Problem Statement
Search Suggestions System
You get a list of product names and a search word. As someone types the search word one letter at a time, you want to show up to three products that start with whatever they have typed so far. The part typed so far is called the prefix, which just means the letters at the start of a word. For example, after typing "mo", the prefix is "mo" and you show products that begin with "mo". If more than three products match a prefix, you show the three that come first in dictionary order (also called lexicographic order, which is the same a, b, c ordering a dictionary uses). You return one list of suggestions for each letter typed. The clean trick here is to sort the products once, then keep a window of matching products that shrinks as more letters get typed.
Signals to notice
Brute force first
For each prefix, filter and sort all products. Re-filters everything for every keystroke. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Sort products, then build a trie. At each node, store references to up to 3 matching products. As the user types each character, walk one node deeper and return that node's suggestions. build, per character lookup. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on products=["bags","baggage","banner","box","cloths"], searchWord="bags"
sort -> ["baggage","bags","banner","box","cloths"]; left=0, right=4 i=0 c='b': cloths[0]='c'!=b so right=3 (box[0]='b'); left=0. window[0..3], take 3 -> ["baggage","bags","banner"] i=1 c='a': box[1]='o'!=a so right=2 (banner[1]='a'); left=0. window[0..2] -> ["baggage","bags","banner"] i=2 c='g': banner[2]='n'!=g so right=1 (bags[2]='g'); left=0. window[0..1] -> ["baggage","bags"] i=3 c='s': baggage[3]='g'!=s so left=1 (bags[3]='s'); right=1. window[1..1] -> ["bags"] return [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
What must stay true
By sorting products lexicographically before building the trie, the first 3 products reaching each node are automatically the lexicographically smallest. No sorting needed at query time. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
sort(products)
left, right = 0, len(products)-1
for i, c in enumerate(searchWord):
while left<=right and products[left][i] != c: left += 1
while left<=right and products[right][i] != c: right -= 1
result.append(products[left : left + min(3, right-left+1)])Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Storing all matching products at each node — only keep the first 3 to avoid memory waste. Since products are pre-sorted, the first 3 encountered during trie construction are the top 3. The fix is usually to return to the meaning of each move, not just the steps themselves.