Search Suggestions System - Video Solutions

Problem Overview: You are given a list of product names and a search word. As the user types each character of the search word, return up to three lexicographically smallest products that start with the current prefix.

Approach 1: Sorting and Linear Prefix Filtering (Time: O(n log n + m * n), Space: O(1) extra)

Start by sorting the product list lexicographically using sorting. For every prefix of the search word, iterate through the sorted list and collect the first three products that start with that prefix. Because the array is sorted, the first matches you encounter are already the smallest in lexicographical order. The key operation is repeated prefix comparison using string.startswith() or substring checks. This approach is easy to implement and works well when the product list is small, but scanning the full list for every prefix leads to O(m * n) checks where m is the search word length.

Approach 2: Trie Data Structure (Time: O(n * k + m * k), Space: O(n * k))

A more scalable solution uses a Trie to store product names character by character. Each node represents a prefix and stores up to three lexicographically smallest product suggestions that share that prefix. Insert every product into the Trie while maintaining a sorted list of at most three suggestions at each node. When processing the search word, traverse the Trie one character at a time and read the stored suggestions directly from the current node. This avoids scanning the entire product list repeatedly and turns the search process into simple prefix traversal.

The Trie approach leverages prefix sharing between strings, which is exactly what the problem models. It also aligns with typical autocomplete system design. Operations mainly involve character traversal and prefix lookup within the Trie, a common pattern in string and search problems.

Recommended for interviews: The Trie solution is usually what interviewers expect because it models a real-world autocomplete system and achieves predictable performance. The sorting approach still demonstrates good understanding of lexicographical ordering and prefix filtering, so it is a solid starting point during discussion before moving to the optimized Trie-based design.