Search Suggestions System
Problem
searchWord typed one
letter at a time. After each letter, suggest up to three products that start with the
text typed so far, choosing the lexicographically smallest ones. Return the list of
suggestion lists, one per typed letter.[mouse,mobile,monitor,mousepad], "mou"Output[[mobile,monitor,mouse], [mobile,monitor,mouse], [mouse,mousepad]][havana], "tat"Output[[], [], []]1 ≤ n ≤ 1000 · total length of products ≤ 2·104 · products are unique · 1 ≤ searchWord.length ≤ 1000 · lowercase only
Try it yourself
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
}
}
Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.
Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.
Open the Trie guide →Approaches
Brute ForceSort + Scan for Every Prefix
O(L·n log n + n·m2)Space O(n)Sort once so the first matches met are the smallest. For each of the m
prefixes, scan all n products with startsWith and keep the first three.
L = max product length, m = searchWord length.
public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); List<List<String>> result = new ArrayList<>(); for (int i = 1; i <= searchWord.length(); i++) { String prefix = searchWord.substring(0, i); List<String> suggestions = new ArrayList<>(); for (String p : products) { if (p.startsWith(prefix)) suggestions.add(p); if (suggestions.size() == 3) break; } result.add(suggestions); } return result; }
Simple and correct, but rescans every product for every typed letter.
BetterTrie Storing Top-3 per Node
O(L·n log n + S + m)Space O(26·S)Insert the sorted products into a trie; every node keeps the first three words that pass through it — exactly the three smallest with that prefix. Answering is then one step down the trie per typed letter. S = total characters.
public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); Node root = new Node(); for (String p : products) { Node cur = root; for (char c : p.toCharArray()) { if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node(); cur = cur.next[c - 'a']; if (cur.top.size() < 3) cur.top.add(p); // sorted => first 3 are smallest } } List<List<String>> result = new ArrayList<>(); Node cur = root; for (char c : searchWord.toCharArray()) { cur = (cur == null) ? null : cur.next[c - 'a']; result.add(cur == null ? new ArrayList<>() : cur.top); } return result; } private static class Node { Node[] next = new Node[26]; List<String> top = new ArrayList<>(); }
O(1) per keystroke after preprocessing — great for many queries, heavy on memory.
OptimalSort + Shrinking Two Pointers
O(L·n log n + n + m)Space O(n)Keep [l, r] = products matching the prefix so far. For letter
i, advance l and retreat r past products whose
i-th char is missing or different; the survivors stay contiguous because
the array is sorted. Pointers only move inward, so all narrowing costs O(n) total.
public List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); List<List<String>> result = new ArrayList<>(); int l = 0, r = products.length - 1; for (int i = 0; i < searchWord.length(); i++) { char c = searchWord.charAt(i); while (l <= r && (products[l].length() <= i || products[l].charAt(i) != c)) l++; while (l <= r && (products[r].length() <= i || products[r].charAt(i) != c)) r--; List<String> suggestions = new ArrayList<>(); for (int j = l; j <= Math.min(l + 2, r); j++) suggestions.add(products[j]); result.add(suggestions); } return result; }
Dry runsorted = [mobile, monitor, mouse, mousepad], searchWord = "mou"
- i=0 'm'mobilelmonitormousemousepadrall match → take 0..2
- i=1 'o'mobilelmonitormousemousepadrall match → take 0..2
- i=2 'u'mobilemonitormouselmousepadrb,n ≠ u → l=2; take 2..3
No extra structure beyond sorting; linear work after the sort.
Arrays.binarySearch / TreeMap.ceilingKey) and read 3 entries.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Sort + Scan for Every Prefix | O(L·n log n + n·m2) | O(n) |
| Better | Trie Storing Top-3 per Node | O(L·n log n + S + m) | O(26·S) |
| Optimal | Sort + Shrinking Two Pointers | O(L·n log n + n + m) | O(n) |
- Forgetting to sort — “smallest three” is about lexicographic order.
- Stopping early after a prefix has no match — still add an empty list for every remaining letter.
- Not checking
length() <= ibeforecharAt(i)— index out of bounds.
- Ask whether the product list changes; a static list favours sort + pointers, a dynamic one a trie.
- Explain why the matching block stays contiguous in sorted order.
- Mention that storing top-3 lists in trie nodes trades memory for O(1) per keystroke.