Log inSign up
mediumLeetCodeNot Started

Search Suggestions System

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1 · Example 1: Mouse autocomplete:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: - m: [mobile, moneypot, monitor] - mo: [mobile, moneypot, monitor] - mou: [mouse, mousepad] - mous: [mouse, mousepad] - mouse: [mouse, mousepad]

Constraints:

  • 1 <= products.length <= 1000
  • 1 <= products[i].length <= 3000
  • 1 <= sum(products[i].length) <= 2 * 104
  • All the strings of products are unique.
  • products[i] consists of lowercase English letters.
  • 1 <= searchWord.length <= 1000
  • searchWord consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Cache bounded top-K answers directly on Trie nodes.
  • Leverage pre-sorting of inputs to avoid downstream sorting entirely.
  • Design ultra-responsive typing suggestion engines.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Interactive keystroke autocomplete suggesting at most 3 words.
  • Top-3 suggestions must be lexicographically smallest.
  • Query output is a list of lists for each prefix length.

Algorithmic Decision Tree:

  • Sort products alphabetically first.
  • Store a list of up to 3 strings at each Trie node.
  • Step through searchWord: if child exists, append its pre-stored suggestions; else append empty list.

Connected Patterns:

Implement Phone DirectoryImplement Trie (Prefix Tree)Design Add and Search Words

1. Filter and Sort per Keystroke

Intuition

Loop through prefix lengths 1 to searchWord.length(). Collect all products where prod.startsWith(prefix). Sort collected list and slice top 3.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Prefix pref = "".
  2. Step 2: For each char in searchWord: append to pref.
  3. Step 3: Filter matched = [p for p in products if p.startsWith(pref)].
  4. Step 4: Sort matched and take first 3.
  5. Step 5: Append to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
10 vector<vector<string>> result;
11 string pref = "";
12
13 for (char c : searchWord) {
14 pref += c;
15 vector<string> matched;
16 for (const string& p : products) {
17 if (p.rfind(pref, 0) == 0) {
18 matched.push_back(p);
19 }
20 }
21 sort(matched.begin(), matched.end());
22 if (matched.size() > 3) matched.resize(3);
23 result.push_back(matched);
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<string> prods = {"mobile","mouse","moneypot","monitor","mousepad"};
32 auto res = sol.suggestedProducts(prods, "mouse");
33 for (const auto& list : res) {
34 for (const string& w : list) cout << w << " ";
35 cout << endl;
36 }
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(|searchWord| * P log P * L) — Repeats filtering and sorting for every character typed.
  • Space complexity: O(P * L) — Holds matching candidate arrays.

Why Brute Force Doesn't Scale:

With 1,000 keystrokes and 1,000 products, naive search runs 1,000,000 checks.

Pre-caching top 3 items answers each keystroke in under 0.01 milliseconds.

2. Sorted Array Binary Search Range

Intuition

Sort products once in O(P log P * L). For each prefix, use lower_bound to find first product starting with or greater than prefix. Check up to 3 consecutive products from that index.

When to apply: Compact memory alternative avoiding Trie node allocation.

Algorithm

  1. Step 1: Sort products lexicographically.
  2. Step 2: Maintain start = 0.
  3. Step 3: For each char in searchWord: append to prefix.
  4. Step 4: Use lower_bound starting from start to locate first product >= prefix.
  5. Step 5: Collect up to 3 products that start with prefix.
  6. Step 6: Update start to lower_bound index.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
10 sort(products.begin(), products.end());
11 vector<vector<string>> result;
12 string pref = "";
13 int start = 0;
14
15 for (char c : searchWord) {
16 pref += c;
17 start = lower_bound(products.begin() + start, products.end(), pref) - products.begin();
18 vector<string> suggestions;
19 for (int i = start; i < min((int)products.size(), start + 3); i++) {
20 if (products[i].rfind(pref, 0) == 0) {
21 suggestions.push_back(products[i]);
22 } else {
23 break;
24 }
25 }
26 result.push_back(suggestions);
27 }
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<string> prods = {"mobile","mouse","moneypot","monitor","mousepad"};
35 auto res = sol.suggestedProducts(prods, "mouse");
36 for (const auto& list : res) {
37 for (const string& w : list) cout << w << " ";
38 cout << endl;
39 }
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(P log P * L + |searchWord| * log P) — Sorting takes O(P log P * L). Each keystroke binary searches in O(log P * L).
  • Space complexity: O(P * L) — Stores sorted products array.

3. Trie with Cached Top-3 Lexicographical Suggestions

Intuition

Sort products alphabetically. Build a Trie where each node stores children[26] and vector<string> suggestions. During insertion of each sorted product, append the product to curr.suggestions if its size is less than 3. For searchWord, walk the Trie. At each keystroke, if node exists, output its pre-cached suggestions; else output empty lists.

When to apply: Standard production & interview optimal solution for Amazon autocomplete systems.

Algorithm

  1. Step 1: Sort products alphabetically.
  2. Step 2: Build Trie: each TrieNode has children[26] and suggestions list (max size 3).
  3. Step 3: Insert each product: on every visited node, if suggestions.size() < 3, append product.
  4. Step 4: For each char in searchWord: if curr && curr.children[idx], move curr = curr.children[idx] and append curr.suggestions.
  5. Step 5: If null, set curr = null and append empty list.
  6. Step 6: Return result.

Interactive Trace for Top-3 Product Suggestions

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Type 'm'
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'm'
top 3: mobile, moneypot, monitor

Node order shown; add connections to display explicit tree edges.

type 'm': m
Check / comparison
node['m'].suggestions read in O(1)
Decision / next transition
Add top 3 products for 'm'.
Why this step matters

Step 1: Type m. Root advances to child m. Node m contains top 3 cached products: [mobile, moneypot, monitor].

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7struct TrieNode {
8 TrieNode* children[26];
9 vector<string> suggestions;
10 TrieNode() {
11 for (int i = 0; i < 26; i++) children[i] = nullptr;
12 }
13};
14
15class Solution {
16 TrieNode* root;
17
18 void insert(const string& product) {
19 TrieNode* curr = root;
20 for (char c : product) {
21 int idx = c - 'a';
22 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
23 curr = curr->children[idx];
24 if (curr->suggestions.size() < 3) {
25 curr->suggestions.push_back(product);
26 }
27 }
28 }
29
30public:
31 vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
32 sort(products.begin(), products.end());
33 root = new TrieNode();
34
35 for (const string& p : products) insert(p);
36
37 vector<vector<string>> result;
38 TrieNode* curr = root;
39
40 for (char c : searchWord) {
41 int idx = c - 'a';
42 if (curr && curr->children[idx]) {
43 curr = curr->children[idx];
44 result.push_back(curr->suggestions);
45 } else {
46 curr = nullptr;
47 result.push_back({});
48 }
49 }
50 return result;
51 }
52};
53
54int main() {
55 Solution sol;
56 vector<string> prods = {"mobile","mouse","moneypot","monitor","mousepad"};
57 auto res = sol.suggestedProducts(prods, "mouse");
58 for (const auto& list : res) {
59 for (const string& w : list) cout << w << " ";
60 cout << endl;
61 }
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O(P log P * L + Total Chars + |searchWord|) — Sorting takes O(P log P * L). Insertion visits each character once. Query runs in O(|searchWord|) total time.
  • Space complexity: O(Total Chars * 26 + 3 * Nodes) — Nodes store up to 3 string references.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Filter and Sort per KeystrokeO(|searchWord| * P log P * L)O(P * L)For each prefix of searchWord, scan all products, filter matching ones, sort, and take first 3.Re-filtering and re-sorting per character.
2.Better — Sorted Array with Binary Search BoundsO(P log P * L + |searchWord| * log P)O(P * L)Sort products once. For each prefix, binary search lower_bound to find first matching word. Check up to 3 consecutive elements.String comparisons in binary search.
3.Optimal — Trie with Pre-cached Top-3 SuggestionsOptimalO(P log P * L + Total Chars + |searchWord|)O(Total Chars * 26)Sort products. Insert into Trie, appending to node.suggestions while size < 3. Typing answers in O(1) per character.None. Canonical Amazon interview problem.

Common Pitfalls & Crucial Edge Cases

Sorting after filtering on every keystroke

Sorting inside the query loop degrades performance from O(1) to O(P log P).

Not stopping suggestions list at 3

Uncapped lists waste memory and violate the 3-suggestion limit.

Crash on null pointer

Failing to set curr = null after first mismatch causes crash on subsequent characters.

Crucial Edge Cases to Validate:

  • Fewer than 3 products match prefix — Returns all matching products (e.g., 1 or 2).
  • No product matches prefix — Returns empty array [] for that keystroke and all subsequent extensions.
  • Single product matching — Correctly returns single item list across valid characters.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the key optimization: sorting upfront means the first 3 products entering each node during insertion are guaranteed to be the 3 lexicographically smallest.
  2. Highlight how query response time becomes O(1) per keystroke — ideal for live web autocomplete APIs.
  3. Discuss the space vs time trade-off between storing suggestions directly on nodes vs running DFS during queries.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does sorting the products before inserting them into the Trie ensure correct suggestions?

2.What is the query time complexity for each keystroke in the optimal Trie implementation?

Back to DSA Sheet