Search Suggestions System

Problem in plain words

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

For example, with products ["pen", "pencil", "pear"] and the word "pe", both steps suggest ["pear", "pen", "pencil"].

Intuition

After sorting, every product that starts with a given prefix sits in one contiguous block, and the block starts at the first position where the prefix would be inserted. So for each prefix, binary-search that position and look at the next three products; any of them that still start with the prefix are the answer. A trie also solves this, but sorting plus binary search is shorter to write and uses far less memory.

Approach

1. Sort products lexicographically.
2. For each length i from 1 to searchWord.length, let prefix be the first i letters.
3. Find start, the first index whose product is greater than or equal to prefix (a lower bound). Because prefixes only grow, the search can begin from the previous start.
4. Collect products at start, start + 1, start + 2 while they exist and start with prefix.
5. Append that list (possibly empty) to the result.

Dry run

Input: products ["bean", "bagel", "banana", "bolt", "bake"], word "bak". Sorted: bagel, bake, banana, bean, bolt.

Java solution

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        int start = 0;
        for (int i = 1; i <= searchWord.length(); i++) {
            String prefix = searchWord.substring(0, i);
            start = lowerBound(products, start, prefix);
            List<String> suggestions = new ArrayList<>();
            for (int j = start; j < products.length && j < start + 3; j++) {
                if (!products[j].startsWith(prefix)) break;
                suggestions.add(products[j]);
            }
            result.add(suggestions);
        }
        return result;
    }

    // First index in [from, n) whose value is >= target.
    private int lowerBound(String[] arr, int from, String target) {
        int lo = from, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid].compareTo(target) < 0) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Python solution

import bisect


class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        result = []
        start = 0
        prefix = ""
        for ch in searchWord:
            prefix += ch
            start = bisect.bisect_left(products, prefix, start)
            suggestions = []
            for word in products[start:start + 3]:
                if not word.startswith(prefix):
                    break
                suggestions.append(word)
            result.append(suggestions)
        return result

Complexity

Edge cases and common mistakes

• No match: once a prefix matches nothing, every later step must still add an empty list, so the result always has searchWord.length entries.
• Reusing `start`: it is safe because a longer prefix can never sort before a shorter one it extends.
• Taking three neighbours without checking: products after start may not share the prefix; always verify with startsWith.
• Duplicates in the input: identical product names are allowed and both appear in the suggestions.