Design Search Autocomplete System

Table of Contents +

You type into a search box and it suggests full searches before you finish. Those suggestions are not random. They are the most popular searches that start with what you typed. This question asks you to build that suggestion engine, and a trie is the natural home for it.

🎯 The Problem

You have to design a search autocomplete that learns from past searches and suggests the top three.

  • You start with past sentences and how many times each was searched. That count is its hot degree.
  • The user types characters one at a time.
  • After each character, return the three most popular sentences that start with what was typed so far.
  • Rank by hot degree from high to low.
  • If two sentences tie, the one earlier in alphabetical order wins.
  • The character # means the user pressed enter. Save the typed sentence as a new search and return an empty list.
Start:
  "i love you"   -> 5
  "island"       -> 3
  "ironman"      -> 2
  "i love leetcode" -> 2


User types: 'i'  -> ["i love you", "island", "i love leetcode"]
User types: ' '  -> ["i love you", "i love leetcode"]
User types: 'a'  -> []        (no sentence starts with "i a")
User types: '#'  -> []        (saves "i a", returns nothing)

Notice “i love you” with degree 5 ranks first. “island” with degree 3 beats “i love leetcode” with degree 2. The two degree-2 sentences would break ties alphabetically, but here only one survives the prefix.

Here is the trie holding these sentences. Spaces are real characters in the path. The marked nodes hold a finished sentence and its degree.

root

i

space

s

r

...love you (deg 5), love leetcode (deg 2)

...island (deg 3)

...ironman (deg 2)

🐢 Approach 1: Scan and Sort Every Sentence (Brute Force)

The idea in one line: on each keystroke, filter every sentence by the prefix and sort the matches.

The idea:

  • Keep all sentences with their degrees in a list.
  • After each character, walk the whole list.
  • Keep the ones that start with the current prefix.

How it works:

  • Sort the matches by degree, then by alphabet.
  • Return the top three.

Why it is weak:

  • Every keystroke scans and sorts all sentences.
  • With many sentences each keystroke gets slow.
  • The user types fast, so a slow keystroke feels laggy.

Here is the scan-and-sort code:

autocomplete_scan_sort.py
from collections import Counter




class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.counts = Counter(dict(zip(sentences, times)))
        self.prefix = ""


    def input(self, c):
        if c == "#":
            self.counts[self.prefix] += 1
            self.prefix = ""
            return []
        self.prefix += c
        matches = [s for s in self.counts if s.startswith(self.prefix)]
        matches.sort(key=lambda s: (-self.counts[s], s))
        return matches[:3]

⚡ Approach 2: Trie Plus Ranking (Best)

The idea in one line: walk a trie as the user types, then rank only the sentences below the current node.

The idea:

  • Store sentences in a trie. A node can be any character, including a space.
  • At the node where a sentence ends, store the sentence and its degree.

How typing works:

  • Keep a pointer to the trie node for the current prefix.
  • Each new character moves the pointer one child down. Never restart from the top.
  • A missing child means the prefix matches nothing, so return an empty list.

How ranking works:

  • Gather all finished sentences under the current node.
  • Keep the best three with a size-three min-heap, a structure whose smallest item sits on top.
  • The weakest of the current best three is on top, so it is easy to drop. This avoids sorting everything.

How enter works:

  • On #, save the typed sentence. Raise its degree if it exists, else add it with degree one.
  • Reset the typed text and return an empty list.

Here is what happens on each keystroke. The pointer moves, we collect, we rank, we return three.

yes

no

no

yes

read next character

is it the # enter key?

save sentence, raise degree, reset

move trie pointer to child

child exists?

return empty list

collect sentences below, rank, return top 3

Steps to Solve

  1. Build a trie. At each sentence-end node, store the sentence and its degree.
  2. Keep a pointer to the current node and a buffer of the typed characters.
  3. On a normal character, move the pointer to that child. If missing, remember the prefix matches nothing.
  4. Collect every finished sentence under the current node.
  5. Rank by degree high to low, breaking ties by alphabetical order, and return the top three.
  6. On #, save the typed sentence (raise its degree or add it), reset the buffer, and return an empty list.

This Python version keeps degrees in a dictionary and sorts the matches by the ranking key on each keystroke.

autocomplete.py
class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.degree = {}                 # sentence -> hot degree
        for s, t in zip(sentences, times):
            self.degree[s] = t
        self.typed = ""                  # what the user has typed so far


    def input(self, ch):
        if ch == "#":                    # enter pressed
            self.degree[self.typed] = self.degree.get(self.typed, 0) + 1
            self.typed = ""              # reset buffer
            return []
        self.typed += ch                 # add the new character
        prefix = self.typed
        # keep sentences that start with the prefix
        hot = [s for s in self.degree if s.startswith(prefix)]
        # higher degree first, ties broken alphabetically
        hot.sort(key=lambda s: (-self.degree[s], s))
        return hot[:3]                   # top three




sentences = ["i love you", "island", "ironman", "i love leetcode"]
times = [5, 3, 2, 2]
ac = AutocompleteSystem(sentences, times)
print(ac.input("i"))
print(ac.input(" "))
print(ac.input("a"))
print(ac.input("#"))

The output of the above code will be:

['i love you', 'island', 'i love leetcode']
['i love you', 'i love leetcode']
[]
[]

Let us read the Python input method line by line, since it carries the ranking rule.

if ch == "#" is the enter case. The line self.degree[self.typed] = self.degree.get(self.typed, 0) + 1 saves the typed sentence. get(self.typed, 0) reads the old degree or zero if it is new, then we add one. We then reset self.typed to an empty string and return an empty list, because enter ends a search.

For a normal character, self.typed += ch grows the typed text. The line hot = [s for s in self.degree if s.startswith(prefix)] keeps only the sentences that start with what was typed. startswith is the prefix test.

The ranking is one line. hot.sort(key=lambda s: (-self.degree[s], s)). The key is a pair. The first part -self.degree[s] is the negative degree, so a higher degree sorts earlier. The second part s is the sentence itself, so ties fall back to alphabetical order. Python sorts by the first part, then the second part, which is exactly the rule. Finally return hot[:3] returns the top three.

We used a dictionary and a full sort here to keep the code clear. The trie plus a size-three min-heap is the production version, and it avoids re-scanning every sentence and sorting all of them on each keystroke.

⏱️ Time and Space Complexity

The simple version scans every stored sentence and sorts the matches on each keystroke. Let N be the number of sentences and K the number that match. That sort costs about K log K per keystroke. The trie version moves the pointer in one step per character. It then collects only the sentences under the current node and keeps the best three with a small heap, so it avoids touching unrelated sentences.

Approach Time per keystroke Space Complexity
Scan and sort all sentences O(N + K log K) O(total letters)
Trie pointer plus size-3 heap O(P + K log 3) O(total letters)

Tip

The detail interviewers love here is the ranking key. Say it as one sentence. Sort by degree high to low, and break ties by alphabetical order. Then mention that a size-three heap keeps the top three without sorting everything.

🧩 Key Takeaways

  • ✅ Store sentences in a trie and keep the sentence and its degree at the end node.
  • ✅ Keep a pointer to the current prefix node so each keystroke is one step down.
  • ✅ Rank by degree high to low, and break ties by alphabetical order.
  • ✅ A size-three min-heap keeps the best three without sorting every match.
  • ✅ On #, save the typed sentence, raise its degree or add it, then reset and return nothing.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the hot degree of a sentence mean?

    Why: The hot degree is the count of how often a sentence was searched. Higher means more popular.

  2. 2

    How are suggestions ranked when two sentences have the same degree?

    Why: Ties in degree are broken by normal alphabetical order, so the earlier word wins.

  3. 3

    What happens when the input character is '#'?

    Why: The '#' means enter. We store the sentence, raise or set its degree, reset the buffer, and return nothing.

  4. 4

    Why use a size-three min-heap during ranking?

    Why: A size-three min-heap lets us hold the top three and drop the weakest, avoiding a full sort.

Score: 0 / 4

🚀 What’s Next?

Previous Word Search II Next Find Median from Data Stream