#1268 Search Suggestions System
the problem
In plain words
After each character typed of searchWord, suggest up to 3 products (lexicographically smallest) that start with the typed prefix. Return the list of suggestion lists.
in products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
out [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
in products = ["havana"], searchWord = "tatiana"
out [[],[],[],[],[],[],[]]
- 1 ≤ products.length ≤ 1000
- 1 ≤ Σ products[i].length ≤ 2·10⁴
- All products unique, lowercase
- 1 ≤ searchWord.length ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTrie (prefix tree)Binary search (exact & bounds)
Sorted order does the heavy lifting: words with the same prefix form one contiguous block, and its first 3 entries are the answer. A trie that stores the first 3 words seen at each node (inserting in sorted order) returns each answer in O(1).
solutions
From brute force to optimal
Sort products; for each typed prefix, scan from the start and take the first 3 matches.
- Sort products.
- For len = 1..m: scan all products, keep the first 3 that start with the prefix.
Sorting compares strings of length ≤ L; then m prefixes × n products × a startsWith of up to m chars.
The sorted copy (output excluded).
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { String[] sorted = products.clone(); Arrays.sort(sorted); List<List<String>> result = new ArrayList<>(); for (int len = 1; len <= searchWord.length(); len++) { String prefix = searchWord.substring(0, len); List<String> picks = new ArrayList<>(); for (String p : sorted) { // rescan everything per prefix if (picks.size() == 3) break; if (p.startsWith(prefix)) picks.add(p); } result.add(picks); } return result; }}The matches for a prefix start at the lower bound of the prefix in the sorted array; take up to 3 from there.
- Sort products.
- For each prefix: lowerBound(prefix) = first product ≥ prefix.
- Take the next ≤ 3 products while they start with the prefix.
m binary searches of log n string comparisons, each up to m characters.
The sorted copy; no extra structure.
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { String[] sorted = products.clone(); Arrays.sort(sorted); List<List<String>> result = new ArrayList<>(); for (int len = 1; len <= searchWord.length(); len++) { String prefix = searchWord.substring(0, len); int start = lowerBound(sorted, prefix); // first product >= prefix List<String> picks = new ArrayList<>(); for (int i = start; i < sorted.length && i < start + 3; i++) { if (!sorted[i].startsWith(prefix)) break; // left the prefix block picks.add(sorted[i]); } result.add(picks); } return result; } private int lowerBound(String[] a, String key) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid].compareTo(key) < 0) lo = mid + 1; else hi = mid; } return lo; }}Insert products in sorted order; every node keeps the first 3 words that pass through it. Then walk searchWord.
- Sort products.
- Insert each product; at every node on its path, add it to
topiftop.size() < 3. - Walk searchWord letter by letter, outputting
node.top; once a letter is missing, output empty lists.
Sort, then each product letter is inserted once (S total), and each typed letter is one step.
Trie nodes, each with ≤ 3 references to existing strings.
class Solution { private static class Node { Node[] children = new Node[26]; List<String> top = new ArrayList<>(3); // first 3 words (alphabetically) below this node } public List<List<String>> suggestedProducts(String[] products, String searchWord) { String[] sorted = products.clone(); Arrays.sort(sorted); // insert in order → first 3 seen are the smallest Node root = new Node(); for (String p : sorted) { Node cur = root; for (char ch : p.toCharArray()) { int i = ch - 'a'; if (cur.children[i] == null) cur.children[i] = new Node(); cur = cur.children[i]; if (cur.top.size() < 3) cur.top.add(p); } } List<List<String>> result = new ArrayList<>(); Node cur = root; for (char ch : searchWord.toCharArray()) { cur = (cur == null) ? null : cur.children[ch - 'a']; result.add(cur == null ? new ArrayList<>() : cur.top); // dead end stays dead } return result; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: "lexicographically smallest 3" means sort first, in every approach.
- Sort + binary search is a perfectly strong answer with less memory; offer the trie as the design you'd use for a live typeahead with many queries.
- Note the dead-end rule: once a prefix has no match, every longer prefix has none either.
traps
- Forgetting to output an empty list for every remaining character after a dead end.
- Collecting all matches with a DFS and sorting them per query — correct, but much slower than storing top 3.
what they ask next
Follow-ups
Suggestions ranked by popularity instead of alphabetically?
Store a small min-heap (or sorted list) of the top-k by score on each node; update on insert. Real typeahead systems precompute this.
before you submit
Edge cases to test
- The typed word leaves every product after some letter → empty lists for all remaining letters.
- Fewer than 3 matches → return just those.
- A product that is a prefix of another ("co", "code") → it sorts first.
practise next
Similar problems
- #208Implement Trie (Prefix Tree)Mediumin Tries
- #35Search Insert PositionEasyin Binary Search
- #347Top K Frequent ElementsMediumin Heaps