Search Suggestions System (LeetCode 1268)

The problem

You get a list of product names and a search word that the user types one letter at a time. After each letter, return up to three products that start with what has been typed so far, choosing the alphabetically smallest ones. Return one list of suggestions per letter.

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

After m and mo, every product matches, so you show the three smallest. From mou onwards, only mouse and mousepad match.

How to think about it

Start with brute force. For each prefix, scan every product, keep the ones that start with it, sort them, and take three. That is O(L · n log n) for a search word of length L and n products, with a lot of repeated sorting.

The key insight: in sorted order, all words with a given prefix sit in one contiguous block. Sort the products once. Every word starting with mou lies together, and the block starts exactly where "mou" itself would be inserted. bisect_left(products, prefix) finds that position in O(log n) comparisons. The smallest three matches are then simply the next three products, as long as they still start with the prefix.

Why only check three. If the product at position i + 1 does not start with the prefix, nothing after it can either, because they are sorted. So looking at products[i:i + 3] and filtering is enough.

Which pattern is this? Typeahead is the classic trie application, and the lesson’s tell (“autocomplete”, “prefix”) points there. The pure-trie version stores the top three words at each node so every keystroke is one step down the trie. The sorted-plus-binary-search version is shorter to write and has the same feel: find the prefix’s region, read the first three.

Approach

1. Sort products.
2. Build prefix one character at a time from searchWord.
3. For each prefix, find i = bisect_left(products, prefix), the first position not smaller than the prefix.
4. Look at products[i:i + 3] and keep the ones that start with prefix.
5. Append that list to the result.

Solution

def suggestedProducts(products, searchWord):
    products.sort(); res = []; prefix = ""
    import bisect
    for ch in searchWord:
        prefix += ch; i = bisect.bisect_left(products, prefix)  # start of the prefix block
        cur = []
        for p in products[i:i + 3]:                              # at most three candidates
            if p.startswith(prefix): cur.append(p)
        res.append(cur)
    return res
# suggestedProducts(["mobile","mouse","moneypot","monitor","mousepad"],"mouse")
#   -> [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],
#       ["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Dry run

Sorted products: mobile, moneypot, monitor, mouse, mousepad (indices 0 to 4).

Complexity

• Time: O(n log n · M) to sort, where M is the product length (string comparisons are not O(1)). Then each of the L prefixes costs O(log n · L) for the binary search plus O(L) to check three candidates.
• Space: O(1) extra beyond the sort and the output. A trie with cached top-3 lists uses O(total characters) instead but answers each keystroke in O(1) after one step.

Edge cases and pitfalls

• No matches (["havana"] with "tatiana") gives an empty list for every letter, not a missing entry.
• Fewer than three matches is handled by the startswith filter.
• Forgetting to sort breaks both the binary search and the “smallest three” rule.
• Duplicates are allowed and appear as separate suggestions.

Related problems

• Implement Trie (Prefix Tree) (LeetCode 208): the structure behind the pure-trie typeahead.
• Search Insert Position (LeetCode 35): exactly what bisect_left computes.
• Map Sum Pairs (LeetCode 677): another “everything with this prefix” query.