Search Suggestions System — Trie Powered Autocomplete

Problem Statement#

LeetCode 1268 — Search Suggestions System | Difficulty: Medium

You are given an array of strings products and a string searchWord. Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have a common prefix with the search word. If there are more than three products with a common prefix, return the three lexicographically smallest.

Return a list of lists of the suggested products after each character of searchWord is typed.

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 10^4
• 1 <= searchWord.length <= 1000
• All products and searchWord are lowercase English letters.

Examples:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
 ["mobile","moneypot","monitor"],
 ["mobile","moneypot","monitor"],
 ["mouse","mousepad"],
 ["mouse","mousepad"],
 ["mouse","mousepad"]
]

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Why This Problem Matters#

This is the FAANG autocomplete prototype. Amazon, Google, Bloomberg, and Uber ask it because real product-search systems literally implement this pattern at scale — typeahead suggestions on every search box you have ever used. The problem combines three core skills: building a trie, sorting strings lexicographically, and serving prefix queries efficiently.

Two solutions are commonly accepted: sort + binary search, and trie with sorted top-3 per node. The trie variant is what we focus on because it scales to streaming products, real-time updates, and personalised ranking — capabilities the binary-search method lacks.

The Core Insight#

After sorting the products lexicographically, every prefix's top-3 lexicographically smallest matches are the first three products in the sorted list whose names begin with that prefix. This gives us two clean approaches:

1. Sort + binary search: sort once, then for each prefix run a bisect_left to find the leftmost match and take up to three from there.
2. Trie with cached suggestions: insert products in sorted order, and at every node along the insert path, append the product to that node's suggestion list — but only if the list has fewer than three entries. Querying is then a simple walk.

The trie approach pre-computes results so each prefix lookup is O(L) regardless of how many products share that prefix. This is the production-friendly choice.

Visual Dry Run#

Sorted products: ["mobile","moneypot","monitor","mouse","mousepad"]. Inserting in this order, each node along the path collects up to 3 suggestions:

root
 └── m → suggestions=[mobile, moneypot, monitor]
       └── o → suggestions=[mobile, moneypot, monitor]
             ├── b → ... → e → [mobile]
             ├── n → ... [moneypot, monitor]
             └── u → s → e → [mouse, mousepad]
                       └── p → a → d → [mousepad]

Query "mouse" character by character:

'm'   → [mobile, moneypot, monitor]
'mo'  → [mobile, moneypot, monitor]
'mou' → [mouse, mousepad]
'mous'→ [mouse, mousepad]
'mouse'→[mouse, mousepad]

After typing 'mou' we leave the m→o→b/n branches behind, and only the u-subtree remains — its cached top-3 is [mouse, mousepad].

Solution (Optimal) — Trie with Cached Top-3#

Python#

class TrieNode:
    __slots__ = ("children", "suggestions")
    def __init__(self):
        self.children = {}
        self.suggestions: list[str] = []   # up to 3, lex-smallest
 
class Solution:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        products.sort()                    # lex order — critical
        root = TrieNode()
 
        # Insert every product, caching top-3 along its path
        for p in products:
            node = root
            for ch in p:
                node = node.children.setdefault(ch, TrieNode())
                if len(node.suggestions) < 3:
                    node.suggestions.append(p)
 
        result: list[list[str]] = []
        node = root
        dead = False
        for ch in searchWord:
            if not dead and ch in node.children:
                node = node.children[ch]
                result.append(node.suggestions)
            else:
                dead = True
                result.append([])         # no further matches possible
        return result

JavaScript#

var suggestedProducts = function (products, searchWord) {
  products.sort();
  const root = { children: {}, suggestions: [] };
 
  for (const p of products) {
    let node = root;
    for (const ch of p) {
      if (!node.children[ch]) node.children[ch] = { children: {}, suggestions: [] };
      node = node.children[ch];
      if (node.suggestions.length < 3) node.suggestions.push(p);
    }
  }
 
  const result = [];
  let node = root;
  let dead = false;
  for (const ch of searchWord) {
    if (!dead && node.children[ch]) {
      node = node.children[ch];
      result.push(node.suggestions);
    } else {
      dead = true;
      result.push([]);
    }
  }
  return result;
};

Alternative — Sort + Binary Search#

from bisect import bisect_left
class Solution2:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        products.sort()
        out, prefix = [], ""
        for ch in searchWord:
            prefix += ch
            i = bisect_left(products, prefix)
            out.append([p for p in products[i : i + 3] if p.startswith(prefix)])
        return out

Complexity#

• Trie build: O(M times K) where M is total characters across products.
• Trie query: O(L) per character of searchWord, total O(searchWord length).
• Sort + bisect: O(M log N) sort + O(L^2 log N) queries (string compare in bisect is O(L)).
• Space: O(M) for the trie.

Common Mistakes#

1. Not sorting products first — top-3 must be lexicographic; insertion order otherwise is arbitrary.
2. Storing all matches per node, then sorting at query time — wastes O(N times L) memory for no benefit.
3. Failing to short-circuit after the first dead prefix — once a prefix has zero matches, every longer prefix also has zero matches; mark dead = True and return empty thereafter.
4. Using append past size 3 — the cached list must stay capped at 3 to bound memory.
5. Returning sliced suggestions from the trie — return the cached list directly to avoid allocation churn.
6. Forgetting case sensitivity — problem says lowercase only; if extending to mixed case, normalise on insert and query.

Interview Tips#

• Mention both approaches: sort + bisect and trie. Pick trie if asked to scale or support streaming inserts.
• Justify caching top-3 per node — it converts query into O(L) regardless of branching.
• Discuss the dead flag optimisation — it caps total work at O(L) even for adversarial searches.
• Walk through how you would extend this to ranked autocomplete (e.g. by popularity) — store a heap per node instead of a sorted list.
• Mention that real systems use compressed tries / DAWGs to fit billions of products.

Follow-up Questions#

• What if the dataset is huge and you cannot sort it? Use a min-heap of size 3 at each trie node and insert all products in any order.
• What about ranking by popularity, not lex order? Store frequency counts per terminal and use a top-3 max-heap per node keyed on frequency.
• Streaming inserts? Insert each new product and update the cached suggestions along its path; cap at 3 and replace the largest if the new product is smaller.
• Multi-language / Unicode? Use a hash map for children instead of a 26-array.
• What if you need top-K, not top-3? Replace the size-3 list with a size-K bounded heap.

Key Takeaways#

• Trie + cached top-3 per node turns autocomplete into O(L) per character.
• Sorting products before insertion makes top-3 a tail-clip during traversal — no sort at query time.
• The dead flag short-circuits the entire query once any prefix becomes unreachable.
• Sort + bisect is a clean alternative for static datasets; trie wins for streaming and ranking.
• This is the production blueprint for typeahead — the same pattern Amazon and Google use under the hood.
• Master this and you have an autocomplete subsystem ready to ship.