Top three suggestions as you type

Sort the words once. For each prefix, binary search the first word that is not smaller than the prefix; matching words follow it contiguously, so check the next three. Sorting costs O(n log n · L) and each prefix O(log n · L). For m typed letters the whole job is O((n + m) log n · L) time, with O(n) space for the sorted copy. A trie storing the top three at each node answers each prefix in O(1) after the build.

Sorted order puts all words sharing a prefix next to each other: the key fact.

Each new letter only narrows the range, so you can also move a lower bound forward without searching again.

Real autocomplete ranks by popularity; the structure is the same with a different sort key.

from bisect import bisect_left


def suggest(words: list[str], typed: str) -> list[list[str]]:
    ordered = sorted(words)
    out: list[list[str]] = []
    for end in range(1, len(typed) + 1):
        prefix = typed[:end]
        first = bisect_left(ordered, prefix)  # matches start here
        window = ordered[first:first + 3]
        picks = [w for w in window if w.startswith(prefix)]
        out.append(picks)
    return out

Common mistakes

• Scanning all words for every prefix.
• Returning words that merely contain the prefix.

Say why sorting makes matches contiguous; the rest follows.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you rank by popularity?

   Show hint

   Store (score, word) at each trie node, keeping the top k by score.

2. What changes with millions of users?

   Show hint

   Precompute top suggestions per prefix offline and serve them from a cache; see the Backend design page.

Similar on Backend: Design search autocomplete The Backend page designs an autocomplete service for many users; this page writes the lookup that returns suggestions for each typed prefix.