How do you solve Search Suggestions System?

Sort products lexicographically. Build a trie where each node stores up to three suggestions. For each product, insert it character by character, appending it to the suggestions list of each node if the list has fewer than three items. Then, for each prefix of searchWord, traverse the trie to collect the stored suggestions. If at any point the prefix path does not exist, append empty lists for remaining prefixes. This approach achieves efficient prefix queries with precomputed suggestions.

What pattern does Search Suggestions System use?

The Pattern: Trie (Prefix Tree with Stored Suggestions) The Heuristic: When needing to retrieve lexicographically smallest suggestions for multiple prefixes, pre-sort inputs and store limited-size suggestion lists at each trie node during insertion to enable O(1) retrieval per prefix without repeated sorting.

Search Suggestions System — Trie

Q: What is the time complexity of Search Suggestions System?

O(n * k + m). Sorting products takes O(n log n). Building the trie takes O(n * k), where n is number of products and k is average length. Each insertion updates up to k nodes, each with O(1) append since suggestions capped at 3. Querying for m prefixes takes O(m). Overall dominated by O(n * k).

Problem

Given an array of strings products and a string searchWord, return a list of lists of strings representing the suggested products after each character of searchWord is typed, where each suggestion list contains at most three lexicographically minimum products starting with the current prefix.

1 ≤ products.length ≤ 1000
1 ≤ products[i].length ≤ 3000
1 ≤ searchWord.length ≤ 1000
All strings consist of lowercase English letters.
All products are unique.

Example

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output:

[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

First, products are sorted lexicographically: ["mobile","moneypot","monitor","mouse","mousepad"]. For each prefix of "mouse": - Prefix "m": suggestions are the first three products starting with 'm': ["mobile","moneypot","monitor"]. - Prefix "mo": same as above. - Prefix "mou": products starting with 'mou' are ["mouse","mousepad"]. - Prefix "mous": same as above. - Prefix "mouse": same as above. The algorithm builds a trie to efficiently track these suggestions for each prefix, enabling quick retrieval of up to three lexicographically smallest matches.

Approach

Straightforward Solution

A brute-force approach would, for each prefix of searchWord, scan all products to find matches and then sort them to pick the top three. This approach is O(m * n * k log k) where m is length of searchWord, n is number of products, and k is average product length, which is inefficient for large inputs.

Core Observation

The problem requires efficient prefix-based retrieval of lexicographically smallest suggestions. A trie is a natural data structure for prefix queries, allowing incremental traversal and storage of suggestions at each node.

Path to Optimal

Preview

Sorting products lexicographically upfront allows building a trie where each node maintains up to three suggestions in sorted order. Inserting products in sorted order ensures suggestions are always the lexicographically smallest…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort products lexicographically. Build a trie where each node stores up to three suggestions…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n * k + m)

Sorting products takes O(n log n). Building the trie takes O(n * k), where n is number of products and k is average length. Each insertion updates up to k nodes, each with O(1) append since suggestions capped at 3. Querying for m prefixes takes O(m). Overall dominated by O(n * k).

Space

O(n * k)

The trie stores nodes for all characters of all products, with each node holding up to three suggestions. This results in O(n * k) auxiliary space, excluding the input and output.

Solution

Python

1class TrieNode:
  def __init__(self):
      self.children = {}
      self.suggestions = []
5
6class Solution:
  def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
      products.sort()
      root = TrieNode()
10
      for word in products:
          node = root
          for c in word:
              if c not in node.children:
                  node.children[c] = TrieNode()
              node = node.children[c]
17
              if len(node.suggestions) < 3:
                  node.suggestions.append(word)
20
      res = []
      node = root
23
      for c in searchWord:
          if node and c in node.children:
              node = node.children[c]
              res.append(node.suggestions)
          else:
              node = None
              res.append([])
31
      return res

Step-by-Step Solution

1

Sort Products and Build Trie with Limited Suggestions per Node

8products.sort()
9root = TrieNode()
11for word in products:
  node = root
  for c in word:
      if c not in node.children:
          node.children[c] = TrieNode()
      node = node.children[c]
      if len(node.suggestions) < 3:
          node.suggestions.append(word)

Objective

To prepare the data structure by sorting products and constructing a trie that stores up to three lexicographically smallest suggestions at each node.

Key Insight

Sorting products upfront ensures that when inserting them into the trie, the first products encountered at each node are the lexicographically smallest. By appending products to the suggestions list only if it has fewer than three items, the trie nodes maintain a capped list of top suggestions without needing to sort repeatedly. This precomputation enables fast prefix queries later.

Interview Quick-Check

Core Logic

Sorting products before insertion guarantees that suggestions stored at each trie node are lexicographically ordered and limited to three, enabling O(1) retrieval.

State & Boundaries

Each trie node stores a dictionary of children and a list of up to three suggestions, ensuring bounded memory per node.

Common Pitfalls & Bugs

Failing to limit suggestions to three per node can cause excessive memory usage and degrade performance.

Complexity

Building the trie takes O(n * k) time, where n is number of products and k is average product length.

2

Traverse Trie to Collect Suggestions for Each Prefix of SearchWord

To efficiently retrieve up to three suggestions for each prefix of searchWord by traversing the trie nodes corresponding to each character.

3

Return the Aggregated List of Suggestions for All Prefixes

To output the final list of suggestion lists corresponding to each prefix of searchWord.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 3 Critical

self.children = {}

Initialize a dictionary that maps characters to child TrieNode objects.

Each trie node must maintain references to its next characters so prefix traversal can proceed efficiently. Using a dictionary keyed by character enables constant-time lookup when inserting products and when traversing prefixes during queries.

Line 4 Critical

self.suggestions = []

Initialize a list to store up to three product suggestions for this prefix.

Each node caches up to three lexicographically smallest products that share the prefix represented by this node. Storing these suggestions during trie construction allows prefix queries to return results instantly without searching or sorting at query time.

Line 8 Critical

products.sort()

Sort the products array lexicographically.

Sorting ensures that when products are inserted into the trie, suggestions stored at each node are the lexicographically smallest, enabling efficient retrieval without further sorting.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why does storing up to three suggestions at each trie node during insertion guarantee lexicographically smallest suggestions for any prefix?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Search Suggestions System from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Search Suggestions System drill

or drill a free problem

1	`class TrieNode:`
2	`def __init__(self):`
3	`self.children = {}`
4	`self.suggestions = []`
5
6	`class Solution:`
7	`def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:`
8	`products.sort()`
9	`root = TrieNode()`
10
11	`for word in products:`
12	`node = root`
13	`for c in word:`
14	`if c not in node.children:`
15	`node.children[c] = TrieNode()`
16	`node = node.children[c]`
17
18	`if len(node.suggestions) < 3:`
19	`node.suggestions.append(word)`
20
21	`res = []`
22	`node = root`
23
24	`for c in searchWord:`
25	`if node and c in node.children:`
26	`node = node.children[c]`
27	`res.append(node.suggestions)`
28	`else:`
29	`node = None`
30	`res.append([])`
31
32	`return res`

8	`products.sort()`
9	`root = TrieNode()`
11	`for word in products:`
12	`node = root`
13	`for c in word:`
14	`if c not in node.children:`
15	`node.children[c] = TrieNode()`
16	`node = node.children[c]`
18	`if len(node.suggestions) < 3:`
19	`node.suggestions.append(word)`