Search Suggestions System (Autocomplete)

▶

Steps

setup

Initialize root node and sort products

Create the root TrieNode with empty children and suggestions. Sort the products lexicographically to ensure suggestions are stored in order.

💡 Sorting products first guarantees that suggestions stored at nodes are always the lexicographically smallest.

Line:

root = TrieNode()
products.sort()

💡 Sorting before insertion simplifies maintaining top 3 suggestions at each node.

insert

Insert 'mobile' into trie - process 'm'

Start inserting the product 'mobile'. From root, check if child 'm' exists. It does not, so create a new node for 'm' and add 'mobile' to its suggestions.

💡 Creating new nodes for characters not yet in the trie builds the structure needed for prefix searches.

Line:

for ch in product:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]
    if len(node.suggestions) < 3:
        node.suggestions.append(product)

💡 Each new character in a product extends the trie, and suggestions are updated at each node.

insert

Insert 'mobile' - process 'o'

From node 'm', check for child 'o'. It does not exist, so create node 'o' and add 'mobile' to its suggestions.

💡 Continuing insertion character by character builds the path for the product in the trie.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Suggestions accumulate at each node along the product's path.

insert

Insert 'mobile' - process 'b'

From node 'o', create child 'b' node and add 'mobile' to its suggestions.

💡 Each new character extends the trie path for the product.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Suggestions are stored at every node along the product's path.

insert

Insert 'mobile' - process 'i'

From node 'b', create child 'i' node and add 'mobile' to its suggestions.

💡 Building the trie path character by character for the product.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Suggestions propagate down the trie path for each product.

insert

Insert 'mobile' - process 'l'

From node 'i', create child 'l' node and add 'mobile' to its suggestions.

💡 Continuing to build the trie path for the product.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Each node along the path stores up to three suggestions including the current product.

insert

Insert 'mobile' - process 'e'

From node 'l', create child 'e' node and add 'mobile' to its suggestions. This completes insertion of 'mobile'.

💡 The last character node completes the product's path in the trie.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 The trie path now fully represents 'mobile' with suggestions at each node.

insert

Insert 'moneypot' - process 'm' (existing node)

Start inserting 'moneypot'. From root, 'm' node exists. Move to 'm' and add 'moneypot' to suggestions (max 3).

💡 Reusing existing nodes avoids duplication and accumulates suggestions.

Line:

for ch in product:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]
    if len(node.suggestions) < 3:
        node.suggestions.append(product)

💡 Nodes can store multiple suggestions up to three, reflecting multiple products sharing prefix.

insert

Insert 'moneypot' - process 'o' (existing node)

From 'm', move to 'o' node which exists. Add 'moneypot' to 'o' node suggestions.

💡 Continuing down existing path, suggestions update with new product.

Line:

node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Suggestions at nodes reflect all products passing through that prefix.

insert

Insert 'moneypot' - process 'n' (new node)

From 'o', 'n' child does not exist. Create node 'n' and add 'moneypot' to suggestions.

💡 New characters create new nodes extending the trie.

Line:

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]
if len(node.suggestions) < 3:
    node.suggestions.append(product)

💡 Trie grows dynamically as new product characters are inserted.

search

Traverse trie for searchWord prefix 'm'

Start searching for prefix 'm' in the trie. Move from root to 'm' node and collect its suggestions.

💡 Prefix traversal uses the trie to quickly find suggestions without scanning all products.

Line:

for ch in searchWord:
    if node and ch in node.children:
        node = node.children[ch]
        result.append(node.suggestions[:])

💡 Suggestions at prefix nodes represent autocomplete options for that prefix.

search

Traverse trie for prefix 'mo'

From 'm', move to 'o' node and collect its suggestions for prefix 'mo'.

💡 Each prefix step narrows suggestions to those matching the prefix.

Line:

if node and ch in node.children:
    node = node.children[ch]
    result.append(node.suggestions[:])

💡 Suggestions remain consistent for prefixes that share the same node.

search

Traverse trie for prefix 'mou'

From 'o', move to 'u' node for prefix 'mou'. Collect suggestions ['mouse', 'mousepad'].

💡 Prefix 'mou' narrows suggestions to products starting with 'mou'.

Line:

if node and ch in node.children:
    node = node.children[ch]
    result.append(node.suggestions[:])

💡 Trie nodes store only relevant suggestions for their prefix.

search

Traverse trie for prefix 'mous'

From 'u', move to 's' node for prefix 'mous'. Collect suggestions ['mouse', 'mousepad'].

💡 Suggestions remain the same as prefix extends but still matches same products.

Line:

if node and ch in node.children:
    node = node.children[ch]
    result.append(node.suggestions[:])

💡 Trie nodes reflect the narrowing prefix search.

search

Traverse trie for prefix 'mouse'

From 's', move to 'e' node for prefix 'mouse'. Collect suggestions ['mouse', 'mousepad'].

💡 Final prefix traversal collects suggestions for full searchWord.

Line:

if node and ch in node.children:
    node = node.children[ch]
    result.append(node.suggestions[:])

💡 Trie efficiently returns top suggestions for each prefix.

search

Final result collected for all prefixes

All prefixes of 'mouse' have been traversed and their suggestions collected. The final result matches expected output.

💡 Collecting suggestions at each prefix node completes the autocomplete search.

Line:

return result

💡 Trie structure enables efficient retrieval of top suggestions for each prefix.

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = TrieNode()  # STEP 1: Initialize root
        products.sort()    # STEP 1: Sort products

        # Build trie
        for product in products:  # STEP 2-10: Insert each product
            node = root
            for i, ch in enumerate(product):
                if ch not in node.children:
                    node.children[ch] = TrieNode()  # STEP: Create new node
                node = node.children[ch]
                if len(node.suggestions) < 3:
                    node.suggestions.append(product)  # STEP: Append suggestion

        result = []
        node = root
        for i, ch in enumerate(searchWord):  # STEP 11-16: Traverse trie for each prefix
            if node and ch in node.children:
                node = node.children[ch]
                result.append(node.suggestions[:])  # STEP: Collect suggestions
            else:
                node = None
                result.append([])
        return result

if __name__ == '__main__':
    sol = Solution()
    products = ["mobile","mouse","moneypot","monitor","mousepad"]
    searchWord = "mouse"
    print(sol.suggestedProducts(products, searchWord))

📊

Search Suggestions System (Autocomplete) - Watch the Algorithm Execute, Step by Step

Watching the trie construction and prefix traversal step-by-step reveals how the algorithm efficiently narrows down suggestions without scanning all products repeatedly.

insert

insert

mobile

m

insert

mobile

mo

insert

mobile

mob

insert

mobile

mobi

insert

mobile

mobil

insert

mobile

mobile*

insert

moneypot

mo

insert

moneypot

mo

insert

moneypot

mon

search

mouse

m

Search: true

search

mouse

mo

Search: true

search

mouse

mou

Search: true

search

mouse

mous

Search: true

search

mouse

mouse*

Search: true

search

mouse*

Search: true

Key Takeaways

✓ Sorting products before insertion ensures suggestions at each node are lexicographically smallest.

Without sorting, maintaining top 3 lex order suggestions at nodes would be more complex.

✓ Trie nodes store up to three suggestions, enabling efficient prefix-based autocomplete without scanning all products.

This reduces search time drastically compared to naive scanning for each prefix.

✓ Traversing the trie for each prefix of the searchWord collects suggestions incrementally, demonstrating the power of prefix trees.

Seeing the active path and suggestions at each step clarifies how autocomplete narrows down options.

Practice

1. What is the time complexity of the optimal trie + BFS approach for finding the longest word in a dictionary with n words, each of average length m?

medium

A. O(n * m + n * 26) because building trie takes O(n*m) and BFS visits each node once

B. O(n * m * 26) since BFS explores all children for each character

C. O(n * m^2) due to checking all prefixes for each word

D. O(n * m log n) due to sorting children at each node during BFS

Solution

1. Step 1: Analyze trie construction

   Inserting n words of length m takes O(n * m) time as each character is processed once.

2. Step 2: Analyze BFS traversal

   BFS visits each node once; each node has up to 26 children, so total BFS cost is O(n * 26) which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie build + BFS traversal sum to O(n*m + n*26) [OK]

Hint: Trie build O(n*m), BFS O(n*26) combined [OK]

Common Mistakes:

• Confusing BFS cost as O(n*m*26)
• Forgetting BFS visits each node once
• Assuming sorting children adds log factor per node

2. What is the time complexity of the optimal Trie + DFS backtracking approach for finding palindrome pairs in a list of n words, each of maximum length k?

medium

A. O(n * k)

B. O(n^2 * k)

C. O(n * k * log n)

D. O(n * k^2)

Solution

1. Step 1: Identify outer and inner loops

   There are n words, each of length k. Trie insertion and search involve iterating over k characters.

2. Step 2: Analyze palindrome checks and DFS

   Palindrome checks on suffixes/prefixes cost O(k) each, done during insertion and search, leading to O(k^2) per word.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie + palindrome checks cause quadratic factor in k, linear in n [OK]

Hint: Palindrome checks inside loops cause k^2 factor [OK]

Common Mistakes:

• Assuming brute force O(n^2 * k)
• Ignoring palindrome check cost
• Confusing log n factor

3. The following code attempts to implement the optimal StreamChecker. Identify the single line that contains a subtle bug that can cause incorrect results or inefficiency.

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in word:  # Bug here: words not reversed
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

medium

A. Line: for ch in word:

B. Line: if len(self.stream) > self.max_len:

C. Line: for ch in reversed(self.stream):

D. Line: if node.is_word:

Solution

1. Step 1: Identify how trie is built

   The code inserts words in forward order instead of reversed order, which breaks suffix matching logic.

2. Step 2: Understand impact on query

   Query traverses reversed stream, expecting reversed trie. Since trie is built forward, traversal fails to find matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversing words during trie build is essential for suffix queries [OK]

Hint: Trie must be built with reversed words for suffix matching [OK]

Common Mistakes:

• Not reversing words when building trie
• Not limiting stream buffer
• Returning false too early

4. Examine the following buggy code snippet for the Word Break problem using iterative DP and a reversed trie. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line initializing dp array without setting dp[0] = True

B. Line inserting reversed words into the trie

C. Line breaking inner loop when character not found in children

D. Line checking if node.is_word and dp[j] before setting dp[i]

Solution

1. Step 1: Identify base case initialization

   dp[0] must be True to represent empty string segmentation. Missing this causes dp[i] never to become True.

2. Step 2: Confirm other lines are correct

   Trie insertion, loop breaks, and condition checks are correct and necessary for correctness and efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[0] = True is essential base case [OK]

Hint: dp[0] must be True to start segmentation [OK]

Common Mistakes:

• Forgetting dp[0] = True
• Not breaking early in inner loop
• Incorrect trie insertion order

5. Examine the following buggy snippet from the Trie + DFS solution. Which line contains the subtle bug that can cause incorrect results or infinite loops?

def dfs(r, c, node):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    char = board[r][c]
    if char == '#' or char not in node.children:
        return
    node = node.children[char]
    if node.word:
        result.append(node.word)
        node.word = None
    # BUG: Missing marking visited cell
    dfs(r+1, c, node)
    dfs(r-1, c, node)
    dfs(r, c+1, node)
    dfs(r, c-1, node)
    # BUG: Missing restoring cell after DFS

medium

A. Line checking if char == '#' or char not in node.children

B. Lines calling dfs recursively without marking visited cells

C. Line appending node.word to result and setting node.word = None

D. Line updating node = node.children[char]

Solution

1. Step 1: Identify missing visited cell marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits and potential infinite loops.

2. Step 2: Identify missing restoring cell state

   Without restoring the cell after DFS, subsequent searches see corrupted board state, causing incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing visited marking causes infinite loops or incorrect word detection [OK]

Hint: Always mark and restore visited cells in DFS [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not restoring board state after DFS
• Appending duplicates without clearing node.word