1268 - Search Suggestions System

Difficulty: Medium | Pattern: Binary Search / Trie | Company tags: Amazon, Google, DoorDash

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 the common prefix with searchWord. If more than three products match, return the three lexicographically minimum products.

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

Example:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
  ["mobile","moneypot","monitor"],   # after 'm'
  ["mobile","moneypot","monitor"],   # after 'mo'
  ["mouse","mousepad"],              # after 'mou' — wait
  ["mouse","mousepad"],              # after 'mous'
  ["mouse","mousepad"]               # after 'mouse'
]

Approach: Sort + Binary Search — O(n log n + m log n)

Key insight: Sort products lexicographically once. For each prefix, binary search to find where products with that prefix start, then take up to 3.

import bisect

def suggestedProducts(products: list[str], searchWord: str) -> list[list[str]]:
    products.sort()
    result = []
    prefix = ""
    
    for c in searchWord:
        prefix += c
        # Find leftmost product with this prefix
        pos = bisect.bisect_left(products, prefix)
        suggestions = []
        
        for i in range(pos, min(pos + 3, len(products))):
            if products[i].startswith(prefix):
                suggestions.append(products[i])
            else:
                break
        
        result.append(suggestions)
    
    return result

Optimized: Narrow Search Range

def suggestedProducts(products: list[str], searchWord: str) -> list[list[str]]:
    products.sort()
    result = []
    lo, hi = 0, len(products) - 1
    
    for i, c in enumerate(searchWord):
        # Narrow window to products that still match
        while lo <= hi and (len(products[lo]) <= i or products[lo][i] != c):
            lo += 1
        while lo <= hi and (len(products[hi]) <= i or products[hi][i] != c):
            hi -= 1
        result.append(products[lo:lo+3])
    
    return result

Dry Run

products = ["mobile","moneypot","monitor","mouse","mousepad"] (sorted: mobile, moneypot, monitor, mouse, mousepad)

After sorting: [mobile, moneypot, monitor, mouse, mousepad]

prefix	bisect_left pos	suggestions
m	0	mobile, moneypot, monitor
mo	0	mobile, moneypot, monitor
mou	3	mouse, mousepad
mous	3	mouse, mousepad
mouse	3	mouse, mousepad

Edge Cases

• searchWord has prefix not in any product → empty list for that step
• Fewer than 3 matching products → return all matching
• All products match every prefix → return 3 lexicographically smallest

Complexity

• Time: O(n log n) sort + O(m × (log n + 3)) searches = O(n log n + m log n)
• Space: O(n) sorted array