Tries crash course ↗ · 178

1268. Search Suggestions System

After each character the user types, return up to 3 products that share the current prefix, in lexicographic order. Sort once, then either narrow a window with two pointers or build a trie that caches the 3 smallest suggestions on every prefix node.

● MediumTrieSortingTypeScript

PROBLEM What we're solving

As the user types searchWord one letter at a time, after each keystroke return up to 3 products that start with the prefix typed so far — the three lexicographically smallest if more than three match. For products = ["mobile","mouse","moneypot","monitor","mousepad"] and searchWord = "mouse", typing m, mo → ["mobile","moneypot","monitor"], then mou, mous, mouse → ["mouse","mousepad"].

KEY IDEA Sort once, then the first 3 matches ARE the answer

Insight → sort the products lexicographically once. After sorting, for any prefix the three answers are simply the first threeproducts that start with it — no per-prefix sorting needed. Build a trie and, while inserting each product (in sorted order), push it onto every prefix node's suggestion list, capping at 3. Because insertions arrive in sorted order, the first three to reach a node are exactly its three smallest matches. Typing then just walks the trie and reads each node's cached list.

RECIPE Sort → build trie with cached top-3 → walk per keystroke

1 · Sort. products.sort()puts everything in global lexicographic order, so "smallest three" becomes "first three encountered."
2 · Insert + cache. For each product, walk it into the trie creating missing nodes. At every node along the way, if its suggestions list has fewer than 3 entries, push the product. Sorted insertion order guarantees these are the smallest.
3 · Type the word. Walk searchWordone char at a time from the root. If the child exists, emit that node's cached suggestions; once the path falls off the trie, every remaining keystroke emits [].
4 · Collect. One sub-list per character typed → a list of searchWord.length lists.

Classic confusion → you do not re-sort at each prefix, and you do not need an isEnd flag here. Because the global sort already orders everything, the first three products to pass through a node are its answer — caching them during insertion is the whole trick. Once the walk hits a missing child, do not reset to the root; the rest of the keystrokes are all empty.

COST Complexity & alternatives

Re-filter per keystroke

O(L · n · m)

Scan all products for each of L prefixes.

Sort + trie (cached top-3)

O(n·m·log n)

Sort dominates; queries are O(L).

Where the time goes

With n products of length up to m and a search word of length L: the sort is O(n·m·log n) (string compares cost up to m), building the trie is O(n·m), and answering all keystrokes is O(L) since each node already holds its top-3. The sort+two-pointer variant skips the trie entirely and is often the cleaner interview answer.

Pattern transfer → caching aggregates on trie nodes powers autocomplete / typeaheadsystems, and the "sort once so first-k = smallest-k" idea recurs in Top K Frequent and merge-style problems. The two-pointer narrowing is the same window-shrinking move as binary search on a sorted array.

RUN IT Sort, cache top-3 per node, then type the word

products =searchWord =

step 0 / 42

STARTStart with 5 products and searchWord = "mouse". First, sort the products lexicographically.

1class TrieNode {
2  children: Record<string, TrieNode> = {};
3  // Up to 3 lexicographically smallest products passing through this node.
4  suggestions: string[] = [];
5}
6 
7▶function suggestedProducts(products: string[], searchWord: string): string[][] {
8  products.sort();                       // global lexicographic order
9 
10  const root = new TrieNode();
11  for (const product of products) {      // insert each product...
12    let node = root;
13    for (const c of product) {
14      if (!node.children[c]) node.children[c] = new TrieNode();
15      node = node.children[c];
16      if (node.suggestions.length < 3)   // ...caching it on every prefix node
17        node.suggestions.push(product);  // products are inserted in sorted
18    }                                    // order, so the first 3 are the answer
19  }
20 
21  const result: string[][] = [];
22  let node: TrieNode | null = root;
23  for (const c of searchWord) {          // type one character at a time
24    node = node ? node.children[c] ?? null : null;
25    result.push(node ? node.suggestions : []);
26  }
27  return result;
28}

productsmobilemousemoneypotmonitormousepad

State

sort

phase

mouse

searchWord

active char / prefixsorted / walkedcached / emittedfell off → empty

slowfast

TYPESCRIPT The solution, annotated

suggestedProducts.ts
class TrieNode {
  children: Record<string, TrieNode> = {};
  // Up to 3 lexicographically smallest products passing through this node.
  suggestions: string[] = [];
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  products.sort();                       // global lexicographic order

  const root = new TrieNode();
  for (const product of products) {      // insert each product...
    let node = root;
    for (const c of product) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
      if (node.suggestions.length < 3)   // ...caching it on every prefix node
        node.suggestions.push(product);  // products are inserted in sorted
    }                                    // order, so the first 3 are the answer
  }

  const result: string[][] = [];
  let node: TrieNode | null = root;
  for (const c of searchWord) {          // type one character at a time
    node = node ? node.children[c] ?? null : null;
    result.push(node ? node.suggestions : []);
  }
  return result;
}

Reading it block by block

The node. Each TrieNode has the usual children map plus a suggestions array holding up to three product names — the cached answer for the prefix that node represents.

Sort first. products.sort()orders everything lexicographically. This is what lets us treat "three smallest matches" as "first three inserted" later on.

Insert and cache. Walk each product into the trie. At every node on the path, if suggestions.length < 3, push the product. Because products arrive sorted, the first three to reach a node are its three lexicographically smallest descendants.

Type the word. Walk searchWord from the root. Following child c lands on the node for the current prefix; emit its cached suggestions. The ?? null guard means once the path falls off, node stays null.

Empty tails. When node is null, every remaining keystroke pushes [] — no product has this prefix, and none ever will as it grows.

Complexity → Sorting is O(n·m·log n) and dominates; building the trie is O(n·m); answering all L keystrokes is O(L) because each node caches its top-3. Space is O(n·m) for the trie (each node stores up to 3 string references).

INTERVIEWFollow-ups they'll ask

"Skip the trie entirely?" After sorting, binary-search the first product ≥ the prefix, then take up to 3 from there that still start with it — the sort+two-pointer approach. Often the cleaner answer.
"Why cache exactly 3?" The problem asks for at most three suggestions, so a node never needs to remember more; capping keeps space at O(3) per node.
"Why does insertion order give the smallest three?" Products are inserted in sorted order, so the first three that pass through any node are, by construction, the three smallest that share that prefix.
"Top-k instead of top-3, or huge product set?" Generalize the cap to k. For an enormous, mostly-static catalog a precomputed trie answers each keystroke in O(1), which is why real typeahead uses this shape.
"Duplicates in products?" Sorting groups them; you can dedupe before inserting, or just let the cap absorb repeats.

OPTIMAL Trie

suggestedProducts.ts
class TrieNode {
  children: Record<string, TrieNode> = {};
  // Up to 3 lexicographically smallest products passing through this node.
  suggestions: string[] = [];
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  products.sort();                       // global lexicographic order

  const root = new TrieNode();
  for (const product of products) {      // insert each product...
    let node = root;
    for (const c of product) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
      if (node.suggestions.length < 3)   // ...caching it on every prefix node
        node.suggestions.push(product);  // products are inserted in sorted
    }                                    // order, so the first 3 are the answer
  }

  const result: string[][] = [];
  let node: TrieNode | null = root;
  for (const c of searchWord) {          // type one character at a time
    node = node ? node.children[c] ?? null : null;
    result.push(node ? node.suggestions : []);
  }
  return result;
}

ALT 1 Sort + binary search / two pointers (no trie)

O(n·m·log n) sort · O(L·(log n + 3)) queries

After the same sort, you don't need a trie at all: for each prefix binary-search the first product ≥ the prefix, then take up to three from there that still start with it. Often the cleaner interview answer.

approach-2.ts
function suggestedProducts(products: string[], searchWord: string): string[][] {
  products.sort();
  const result: string[][] = [];
  let prefix = '';
  let lo = 0;                                  // window can only shrink rightward
  for (const ch of searchWord) {
    prefix += ch;
    // advance lo to the first product still >= prefix
    while (lo < products.length && products[lo] < prefix) lo++;
    const row: string[] = [];
    for (let i = lo; i < products.length && row.length < 3; i++) {
      if (products[i].startsWith(prefix)) row.push(products[i]);
      else break;                              // sorted ⇒ no more matches
    }
    result.push(row);
  }
  return result;
}

Note → The left pointer lonever moves backward because each new character only makes the prefix larger, so matching products can only start later in the sorted array. You could swap the linear advance for a true binary search, but with the monotonic pointer it's already near-linear across all keystrokes.

MNEMONIC The one-liner

"Sort once, then first-3-through-a-node = its answer; cache top-3 on every prefix node while inserting, then just walk and read."

TRIGGERS When you see _ → reach for _

suggestions / autocomplete after each typed char	trie with cached top-k per node
"k lexicographically smallest matches"	sort first → first-k = smallest-k
prefix queries over a fixed dictionary	trie (prefix tree)
sorted array + find window for a prefix	binary search + two pointers

SKELETON The reusable shape

skeleton.ts
products.sort();
const root: Node = { children: {}, sug: [] };
for (const p of products) {
  let n = root;
  for (const c of p) {
    n = (n.children[c] ??= { children: {}, sug: [] });
    if (n.sug.length < 3) n.sug.push(p);   // sorted insert ⇒ first 3 = answer
  }
}
const res: string[][] = [];
let n: Node | null = root;
for (const c of searchWord) {
  n = n ? n.children[c] ?? null : null;
  res.push(n ? n.sug : []);
}
return res;

FLASHCARDS Tap to flip

Why sort the products before building the trie?

So the first three products to pass through any node are its three lexicographically smallest matches — no per-prefix sorting needed.

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Why sort the products first?

QUESTION 02

In the trie approach, what does each node cache?

QUESTION 03

When inserting a product, you push it onto a node’s suggestions only if:

QUESTION 04

While typing searchWord you reach a character with no matching child. What should the rest of the output be?

QUESTION 05

For products = ["mobile","mouse","moneypot","monitor","mousepad"] and prefix "mo", the suggestions are:

QUESTION 06

Overall time complexity of the sort + trie solution?

QUESTION 07

Why is no isEnd flag needed in this problem?

QUESTION 08

#1268 · Search Suggestions SystemAfter each typed character, return up to three lexicographically smallest products sharing the current prefix. A trie caching three suggestions per node (or sorted products narrowed with two pointers) answers every prefix efficiently.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Sort once, then the first 3 matches ARE the answer

RECIPE Sort → build trie with cached top-3 → walk per keystroke

COST Complexity & alternatives

Where the time goes

RUN IT Sort, cache top-3 per node, then type the word

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Trie

ALT 1 Sort + binary search / two pointers (no trie)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _