Search Suggestions System: Trie Meets Binary Search

You are given a list of product names and a search word. As the user types each character of the search word, you need to suggest up to three product names that share the current prefix. The suggestions must be in lexicographic order.

This is LeetCode 1268: Search Suggestions System, and it models the real autocomplete feature you use every day in search engines and e-commerce sites. The problem tests your ability to efficiently narrow down a sorted list using prefixes, and it can be solved with two fundamentally different approaches: sorting with binary search, or a trie.

Why this problem matters

Autocomplete is everywhere. When you type into Google, Amazon, or your IDE, the system is doing exactly what this problem describes: matching a growing prefix against a dictionary and returning the top results. Understanding how to build this efficiently is both a practical skill and a common interview topic.

The problem also sits at an interesting crossroads of data structures. You can solve it with pure sorting and binary search (no extra data structure needed), or you can build a trie for prefix lookups. Both approaches pass on LeetCode, but they teach different lessons about tradeoffs between simplicity and structure.

Approach 1: Sorting with binary search

The key insight is that if you sort the products first, all words sharing a given prefix will be grouped together in a contiguous block. You can use binary search to find where that block starts, then grab the first three entries.

For each character you type, extend the prefix and binary search for it in the sorted list. The first match at the binary search position (and the next two entries, if they also match the prefix) form your suggestions.

def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    prefix = ""
    start = 0

    for ch in searchWord:
        prefix += ch
        i = bisect_left(products, prefix, start)
        suggestions = []
        for j in range(i, min(i + 3, len(products))):
            if products[j].startswith(prefix):
                suggestions.append(products[j])
        result.append(suggestions)
        start = i

    return result

This works because bisect_left finds the insertion point for the prefix in the sorted list. Any product that starts with the prefix will appear at or after this position. We check up to three candidates starting from that position.

Notice the start = i optimization. Since each new prefix is longer than the previous one, the matching products can only appear at or after the previous starting position. This narrows the binary search range as you type.

Approach 2: Trie-based solution

If you have solved Implement Trie, this approach will feel natural. Build a trie from all products, then walk it character by character as you type the search word. At each node, collect up to three words from the subtree below.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []

class Solution:
    def suggestedProducts(self, products, searchWord):
        products.sort()
        root = TrieNode()

        for product in products:
            node = root
            for ch in product:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
                if len(node.suggestions) < 3:
                    node.suggestions.append(product)

        result = []
        node = root
        for i, ch in enumerate(searchWord):
            if node and ch in node.children:
                node = node.children[ch]
                result.append(node.suggestions)
            else:
                node = None
                result.append([])

        return result

The trick here is that we store up to three suggestions directly in each trie node during insertion. Since we insert the products in sorted order, the first three products that pass through any node are automatically the lexicographically smallest ones. This avoids a separate DFS to collect suggestions at query time.

Which approach should you use?

Both approaches have their strengths:

For an interview, the sorting approach is usually the better choice because it is shorter and easier to get right under pressure. But if the interviewer asks for a follow-up (like handling dynamic product additions), the trie approach is more flexible.

Step-by-step walkthrough

Let's trace through the example with products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"] and searchWord = "mouse". After sorting, the products are ["mobile", "moneypot", "monitor", "mouse", "mousepad"].

Complexity analysis

Let n be the number of products, m be the maximum product length, and s be the length of the search word.

Sorting approach: The dominant cost is sorting at O(n log n). Each of the s characters triggers a binary search costing O(log n), plus O(m) for the startsWith check on up to 3 candidates. Total query time is O(s * (log n + m)), but since s <= m, this simplifies to O(n log n + s * m) overall.

Trie approach: Building the trie takes O(n * m) since we insert every character of every product. Querying takes O(s) since we just walk down the trie, one node per character, and the suggestions are precomputed. The space cost is the trie itself, which in the worst case stores every character.

Building blocks

This problem combines two reusable patterns that appear across many LeetCode problems.

1. Binary search on a sorted collection

The core idea of sorting data and using bisect_left to find a prefix boundary is the same pattern you see in Binary Search problems. The sorted order guarantees that all matching products form a contiguous range, and binary search finds the start of that range in O(log n) time.

i = bisect_left(products, prefix, start)

This single line does the heavy lifting. It finds where prefix would be inserted in the sorted list, which is exactly where matching products begin. This pattern applies to any problem where you need to find a range of values sharing a common prefix or falling within a bound.

2. Trie prefix traversal

The character-by-character walk down a trie is the same traversal you build in Implement Trie. Here, the twist is that you precompute suggestions during insertion rather than collecting them during queries. This "store results at nodes" optimization is useful whenever your queries follow insertion paths.

node = node.children[ch]
result.append(node.suggestions)

Once the trie is built, each query step is just a dictionary lookup and a list read. No recursion, no DFS. The suggestions are already waiting at the right node.

Edge cases

Before submitting, verify these scenarios:

• Search word longer than any product: once no products match, every remaining character returns an empty list. The trie approach handles this naturally when node becomes None. The binary search approach handles it when startsWith fails for all candidates.
• Fewer than 3 matching products: you return however many match, not necessarily three. Both approaches handle this by checking bounds before adding to the suggestion list.
• Products with identical prefixes: for example, ["aa", "aaa", "aaaa"] with search word "aaaa". Each step should still return the first three matches. The sorted order ensures correctness.
• Single product, single character: the minimal case. Make sure your loop handles one iteration and one candidate.
• All products share the search word as a prefix: for example, products = ["mousetrap", "mousepad", "mouseover", "mouse"] with searchWord = "m". You return the first three from the sorted list at every step.

From understanding to recall

You have seen two approaches to this problem. The sorting solution is compact and relies on a pattern you already know from binary search problems. The trie solution is more involved but demonstrates a powerful technique for prefix-based lookups.

The real question is: can you write either solution from memory during an interview? The binary search version has subtle details (using bisect_left, checking startsWith on only 3 candidates, updating the start bound). The trie version requires you to know the node structure and the trick of precomputing suggestions during insertion.

Spaced repetition closes that gap. You practice writing the bisect_left loop and the trie insertion from scratch at increasing intervals. After a few reps, you stop thinking about the mechanics and start thinking about the problem. That is when you are ready.

These two building blocks, binary search on sorted data and trie prefix traversal, are part of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Implement Trie - Build the trie data structure from scratch, the foundation for the trie-based approach to this problem
• Binary Search - The core binary search pattern used in the sorting-based approach
• Top K Frequent Words - Another problem that combines sorting with string processing to return ranked results

CodeBricks breaks the search suggestions system problem into its binary search and trie traversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a prefix matching problem shows up in your interview, you do not think about it. You just write it.