1268. Search Suggestions System

1268

MediumTrie and Advanced String SearchTrie (prefix tree)Prefix-tree suggestions

Search Suggestions System

Given an array of product names and a search word typed one character at a time, after each character return up to three products from the list that share the currently typed prefix. When more than three match, return the three that are smallest in lexicographic order. Produce one such list for every prefix of the search word.

Open official problem prompt ↗

In plain English

For every prefix of the search word, list the (up to three) lexicographically smallest product names that begin with that prefix.

Picture it like this

It works like a search box autocomplete: each keystroke drills one level deeper into a filing cabinet whose drawers are already sorted, and you read off the top three folders in the drawer you land in.

Example

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Why: After typing "m" and "mo" the three smallest matches are mobile, moneypot, monitor; once "mou" narrows it, only mouse and mousepad remain.

Constraints

1 <= products.length <= 10001 <= products[i].length <= 30001 <= sum of products[i].length <= 2 * 10^4products[i] consists of lowercase English letters1 <= searchWord.length <= 1000searchWord consists of lowercase English letters

Pattern lesson

See the pattern, then code

Prefix-tree suggestions

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. If products are sorted first, the first three words that pass through any trie node are automatically the three lexicographically smallest sharing that prefix, so each node can precompute its own answer.

New words, made simpleKnow these before the algorithm

Trie: A tree where each edge is a character, so a root-to-node path spells a prefix shared by all words in that subtree.
Lexicographic order: Dictionary order; sorting strings this way means the first ones seen are the smallest.
Prefix: The leading run of characters typed so far, e.g. 'mou' for 'mouse'.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Filter and sort per keystroke

Re-scanning every product for each of the m prefixes is wasteful and repeats identical work.

For each prefix, scan all products, keep those that start with it, sort, and take three.

Time O(m * n * L)Space O(n)

Best choiceSorted trie with cached top-3

Sorting guarantees the cached three are the smallest, and each query character is a single O(1) hop.

Sort once, insert into a trie, and store the first three passing words at each node; then just walk the trie as the word is typed.

Time O(n * L * log n)Space O(n * L)

The rule we keep true

Invariant

Because products were inserted in sorted order, the list cached at any trie node holds the three lexicographically smallest inserted words that pass through it.

Why this is correct

Reasoning

Every word sharing a prefix passes through the node for that prefix. Inserting in sorted order means the first three arrivals are exactly the three smallest, so reading the cache answers the query correctly; once a typed character has no edge, no product can match any longer prefix, so all remaining answers are empty.

The algorithm in three movesSay these aloud before coding

1Sort products so smaller words are inserted first

node 'm' cache = [mobile, moneypot, monitor]

2Insert each word into a trie, caching up to three words at every node it passes through

node 'mou' cache = [mouse, mousepad]

3Walk the trie one character per typed letter

typed 'mouse' -> [mouse, mousepad]

4Emit the cached list at the current node, or an empty list once the path breaks

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

mobile0

moneypot1

monitor2

mouse3

mousepad4

1 · Readprefix 'm'

2 · AskWhich words pass through node m first?

3 · Update statecache = [mobile, moneypot, monitor]

4 · ResultAppend [mobile, moneypot, monitor]

Key takeaway

Products shown sorted; after prefix 'mou' only the last two survive at that trie node.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sort first
Guarantees that the earliest words to reach any node are the lexicographically smallest.
2
Lines 5-13Build trie with cached answers
As each word threads down its path, append it to any node whose cache still has fewer than three entries.
3
Lines 15-24Answer each keystroke
Hop to the child for the typed character and read its cache; once a hop fails, mark matched False so every later prefix yields [].

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Fewer than three products match a prefix (return however many exist)
The typed word diverges from all products partway through (remaining answers are empty lists)
A product exactly equals the search word (it still appears in its own prefixes' caches)
Duplicate product names sort adjacently and both can be cached

Common beginner mistakes

Forgetting to sort, which breaks the 'first three are smallest' guarantee
Continuing to search the trie after a prefix has no matching edge instead of emitting empty lists
Capping the cache incorrectly so a node stores more or fewer than three words
Comparing by length instead of lexicographic order when choosing the three

Check your understanding

Why does inserting products in sorted order let each node keep only its first three words?

PyPython 3 · solution.py

Optimal

1class Solution:2    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:3        products.sort()4        trie: dict = {}5        for p in products:6            node = trie7            for ch in p:8                if ch not in node:9                    node[ch] = {"#": []}10                node = node[ch]11                if len(node["#"]) < 3:12                    node["#"].append(p)13        result: list[list[str]] = []14        node = trie15        matched = True16        for ch in searchWord:17            if matched and ch in node:18                node = node[ch]19                result.append(node["#"])20            else:21                matched = False22                result.append([])23        return result

Time complexityO(n * L * log n)Optimized

Space complexityO(n * L)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Search Suggestions System

Search Suggestions System

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search