Problem Description

You need to build a product search suggestion system. Given an array of product names products and a search word searchWord, your system should suggest products as the user types each character of the search word.

The requirements are:

• After typing each character of searchWord, suggest up to 3 products from products that start with the currently typed prefix
• If more than 3 products match the prefix, return the 3 that come first lexicographically (alphabetically)
• Return the suggestions as a list of lists, where each inner list contains the suggestions after typing each character

For example, if products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"] and searchWord = "mouse":

• After typing "m": suggest ["mobile", "moneypot", "monitor"] (3 products starting with "m", sorted alphabetically)
• After typing "mo": suggest ["mobile", "moneypot", "monitor"] (3 products starting with "mo")
• After typing "mou": suggest ["mouse", "mousepad"] (only 2 products start with "mou")
• After typing "mous": suggest ["mouse", "mousepad"]
• After typing "mouse": suggest ["mouse", "mousepad"]

The solution uses a Trie data structure combined with sorting. First, the products are sorted alphabetically. Then a Trie is built where each node stores up to 3 product indices that have the corresponding prefix. When searching, for each character typed, the Trie traversal finds the matching products efficiently. The indices stored in the Trie nodes are then mapped back to the actual product names from the sorted products array.

Intuition

When we need to find products that share a common prefix with what's being typed, the natural data structure that comes to mind is a Trie (prefix tree). A Trie excels at prefix matching because each path from the root to a node represents a prefix, and we can efficiently traverse character by character.

However, we also need to return the lexicographically smallest products when there are more than 3 matches. Rather than sorting products at each node during search time, we can pre-sort the entire products array once. This way, when we insert products into the Trie in sorted order, the first products we encounter for any prefix are automatically the lexicographically smallest ones.

The key insight is to store indices instead of actual product names in the Trie nodes. Since we've pre-sorted the products array, if we store indices [i, j, k] where i < j < k, we know that products[i] comes before products[j] lexicographically, which comes before products[k].

By limiting each Trie node to store at most 3 indices, we automatically maintain the "top 3 lexicographically smallest" products for each prefix. As we build the Trie by inserting products in sorted order, the first 3 products that pass through any node are guaranteed to be the 3 smallest for that prefix.

During the search phase, we simply traverse the Trie following the characters of searchWord. At each step, the current node already contains the indices of up to 3 best matching products, which we can directly add to our result. If at any point a character doesn't exist in the Trie, we know there are no matching products for that prefix and all subsequent prefixes, so we can stop early.

Learn more about Trie, Binary Search, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation consists of two main components: a Trie data structure and the main solution class.

Trie Implementation:

Each Trie node contains:

• children: An array of size 26 (for lowercase letters a-z), where children[i] points to the child node for character 'a' + i. Initially all are None.
• v: A list that stores up to 3 product indices that have the prefix represented by the path to this node.

The insert method adds a word to the Trie:

def insert(self, w, i):
    node = self
    for c in w:
        idx = ord(c) - ord('a')  # Convert character to index (0-25)
        if node.children[idx] is None:
            node.children[idx] = Trie()  # Create new node if needed
        node = node.children[idx]
        if len(node.v) < 3:
            node.v.append(i)  # Store product index (max 3)

For each character in the word, we calculate its index (0-25), create a child node if it doesn't exist, move to that child, and add the product index if we haven't stored 3 products yet.

The search method finds suggestions for each prefix:

def search(self, w):
    node = self
    ans = [[] for _ in range(len(w))]  # Initialize result for each character
    for i, c in enumerate(w):
        idx = ord(c) - ord('a')
        if node.children[idx] is None:
            break  # No products with this prefix
        node = node.children[idx]
        ans[i] = node.v  # Get stored indices for this prefix
    return ans

We traverse the Trie following the search word. If we can't find a character, we stop (remaining results stay empty). Otherwise, we collect the stored indices at each node.

Main Solution:

1. Sort the products: products.sort() ensures lexicographic ordering.

2. Build the Trie: Insert each product with its index in the sorted array:

trie = Trie()
for i, w in enumerate(products):
    trie.insert(w, i)

3. Search and map indices to products:

return [[products[i] for i in v] for v in [trie](/problems/trie_intro).search(searchWord)]

The search returns indices for each prefix, which we map back to actual product names.

Time Complexity:

• Building Trie: O(N * M) where N is the number of products and M is the average length of products
• Sorting: O(N * log N * M) for comparing strings
• Searching: O(L) where L is the length of searchWord
• Total: O(N * log N * M + N * M + L)

Space Complexity: O(N * M) for storing the Trie structure.

Example Walkthrough

Let's walk through a small example with products = ["apple", "apricot", "application"] and searchWord = "app".

Step 1: Sort the products alphabetically After sorting: ["apple", "application", "apricot"]

• Indices: apple → 0, application → 1, apricot → 2

Step 2: Build the Trie

Insert "apple" (index 0):

root
  └─ a: [0]
      └─ p: [0]
          └─ p: [0]
              └─ l: [0]
                  └─ e: [0]

Insert "application" (index 1):

root
  └─ a: [0,1]
      └─ p: [0,1]
          └─ p: [0,1]
              └─ l: [0,1]
                  ├─ e: [0]
                  └─ i: [1]
                      └─ c: [1]
                          └─ a: [1]
                              └─ t: [1]
                                  └─ i: [1]
                                      └─ o: [1]
                                          └─ n: [1]

Insert "apricot" (index 2):

root
  └─ a: [0,1,2]
      └─ p: [0,1,2]
          ├─ p: [0,1]
          │   └─ l: [0,1]
          │       ├─ e: [0]
          │       └─ i: [1]...
          └─ r: [2]
              └─ i: [2]
                  └─ c: [2]
                      └─ o: [2]
                          └─ t: [2]

Step 3: Search for "app"

• Type 'a': Traverse to node 'a', which stores [0,1,2]

  • Map to products: ["apple", "application", "apricot"]

• Type 'p' (prefix "ap"): Traverse to node 'p' under 'a', which stores [0,1,2]

  • Map to products: ["apple", "application", "apricot"]

• Type 'p' (prefix "app"): Traverse to node 'p' under 'ap', which stores [0,1]

  • Map to products: ["apple", "application"]

Final Result: [["apple", "application", "apricot"], ["apple", "application", "apricot"], ["apple", "application"]]

Each inner list represents the suggestions after typing each character. Notice how:

• The Trie stores at most 3 indices per node
• Products are suggested in lexicographic order because we sorted first
• Only products with the exact prefix are returned (e.g., "apricot" doesn't match "app")

Solution Implementation

Time and Space Complexity

Time Complexity: O(L × log n + m)

• Sorting the products array takes O(n × log n × k) where k is the average length of product strings. This can be simplified to O(L × log n) where L is the total length of all product strings.
• Building the Trie requires iterating through all products and inserting each character, which takes O(L) time total.
• Each node stores at most 3 indices in the v list, and appending to this list is O(1).
• Searching in the Trie for the searchWord takes O(m) where m is the length of searchWord.
• Converting the indices back to product strings takes O(m) since each prefix can have at most 3 suggestions.
• Overall time complexity: O(L × log n + L + m) = O(L × log n + m) (since L × log n dominates L).

Space Complexity: O(L)

• The Trie structure can have at most O(L) nodes in the worst case, where each character of every product creates a new node.
• Each node contains an array of 26 pointers to children and a list v that stores at most 3 indices.
• The space for storing indices is O(L) in total across all nodes (at most 3 indices per node, and O(L) nodes).
• The result list for search operation uses O(m) space temporarily.
• Overall space complexity: O(L).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Prefixes When No Matches Exist

A common mistake is not properly handling the case when a character in the search word doesn't exist in the Trie. When we encounter a character that has no corresponding child node, we break out of the loop, but the remaining positions in the result list stay as empty lists (which is correct). However, developers often make mistakes by:

• Trying to continue traversal after hitting a None child
• Not initializing the result list properly with empty lists
• Attempting to access node.product_indices when node is None

Incorrect Implementation:

def search(self, word: str) -> List[List[int]]:
    current_node = self
    suggestions = []  # Wrong: not pre-initialized with empty lists
  
    for position, char in enumerate(word):
        char_index = ord(char) - ord('a')
        current_node = current_node.children[char_index]  # Dangerous: might be None
        suggestions.append(current_node.product_indices)  # Will crash if current_node is None
  
    return suggestions

Correct Implementation:

def search(self, word: str) -> List[List[int]]:
    current_node = self
    suggestions = [[] for _ in range(len(word))]  # Pre-initialize with empty lists
  
    for position, char in enumerate(word):
        char_index = ord(char) - ord('a')
        if current_node.children[char_index] is None:
            break  # Stop searching, remaining positions stay empty
        current_node = current_node.children[char_index]
        suggestions[position] = current_node.product_indices
  
    return suggestions

2. Adding Product Indices Without Checking the 3-Product Limit

Another pitfall is forgetting to limit the number of products stored at each Trie node to 3. Without this check, all matching products would be stored, defeating the purpose of the optimization and potentially returning more than 3 suggestions.

Incorrect Implementation:

def insert(self, word: str, product_index: int) -> None:
    current_node = self
  
    for char in word:
        char_index = ord(char) - ord('a')
        if current_node.children[char_index] is None:
            current_node.children[char_index] = Trie()
        current_node = current_node.children[char_index]
        current_node.product_indices.append(product_index)  # Wrong: no limit check

Correct Implementation:

def insert(self, word: str, product_index: int) -> None:
    current_node = self
  
    for char in word:
        char_index = ord(char) - ord('a')
        if current_node.children[char_index] is None:
            current_node.children[char_index] = Trie()
        current_node = current_node.children[char_index]
        if len(current_node.product_indices) < 3:  # Check limit before adding
            current_node.product_indices.append(product_index)

3. Inserting Products Before Sorting

A critical mistake is building the Trie before sorting the products array. Since we're storing indices and want the lexicographically smallest products, the indices must correspond to the sorted array.

Incorrect Implementation:

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
    trie = Trie()
  
    # Wrong: Building trie before sorting
    for index, product in enumerate(products):
        trie.insert(product, index)
  
    products.sort()  # Sorting after building trie breaks index mapping
  
    suggestion_indices = trie.search(searchWord)
    return [[products[index] for index in indices] for indices in suggestion_indices]

Correct Implementation:

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
    # Sort first to ensure indices correspond to lexicographic order
    products.sort()
  
    trie = Trie()
    for index, product in enumerate(products):
        trie.insert(product, index)
  
    suggestion_indices = trie.search(searchWord)
    return [[products[index] for index in indices] for indices in suggestion_indices]

These pitfalls can lead to runtime errors, incorrect results, or inefficient solutions. Always ensure proper null checking, enforce constraints (like the 3-product limit), and maintain correct index-to-product mapping by sorting before building the data structure.