We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given a list of products and a searchWord, simulate a search box's autocomplete.
After each character of searchWord is typed, return at most three product names that start with the prefix typed so far, in lexicographic order. If fewer than three match, return all of them.
Return a list of suggestion lists - one per typed character, so the result has searchWord.length entries.
A medium trie problem, graded against 6 test cases (3 of them hidden).
A prefix tree for fast string lookup by shared prefix.
Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.
More Trie problems →Every output list must be lexicographic, so sorting the products up front removes ordering from the rest of the problem entirely.
Trie version: insert the sorted products, walk to the node for each prefix, and DFS from it visiting children in sorted character order, stopping after three completions. Because children are visited in order, the first three found are the three smallest - no sorting per query. Each prefix walk continues from the previous node, so the whole search word costs one pass.
Sorted-scan version: after sorting, all products sharing a prefix are contiguous. Binary search the first product `>= prefix` and take up to three consecutive entries that still start with it. Fewer moving parts, and interviewers generally accept it, but say why it works: contiguity is a consequence of the sort, not an assumption.
One detail worth handling deliberately: once a prefix matches nothing, no longer prefix can match either, so the remaining answers are all empty - the `"tatiana"` case, where the trie walk falls off at the first character and everything after is `[]`.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.