Search Suggestions System

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given a list of product names and a search word typed one letter at a time, return, after each letter, up to three product names that start with the typed prefix, in alphabetical order. If fewer than three match, return those that do; if none match, return an empty list for that letter.

    The typeahead box in miniature. It is a natural fit for a trie, and also a nice example of a simpler answer (sort plus binary search) that is just as fast here. Interviewers like to ask for both and then push on scale. Original problem: LeetCode 1268.

    Example

    Each new letter narrows the matches; at "cand" only candle is left.
    Each new letter narrows the matches; at "cand" only candle is left.
    products = [cable, camera, candle, canvas, cap, car, card], searchWord = "cand"
    Output:
    "c"    -> [cable, camera, candle]
    "ca"   -> [cable, camera, candle]
    "can"  -> [candle, canvas]
    "cand" -> [candle]

    Constraints (assumed)

    • Up to 1,000 products, each up to 3,000 lowercase letters; total length up to 2 × 10⁴. The search word is up to 1,000 letters.

    What this question tests

    • Building a trie and storing per-node answers (the top three) so each query step is O(1) to read.
    • Or: using sorted order and binary search, since matches for a prefix form one contiguous block.
    • Handling the moment the prefix stops matching anything.

    Questions to ask first

    1. Is "alphabetical" plain string order? (Here: yes, lowercase letters.)
    2. Can products repeat? (Assume unique; with duplicates, decide whether to show both.)
    3. Will many search words be asked against the same products? That favors precomputing a trie.
    4. Should results be ranked by popularity instead? (Here: no. That is the common follow-up.)