We're building a simple autocomplete feature. As the user types each character of searchWord, we need to find all products that share the same prefix as what's been typed so far, then return up to 3 of them in lexicographic (alphabetical) order.

So if the user types "m", we want the 3 alphabetically smallest products starting with "m". Then they type "o" (prefix is now "mo"), and we want the 3 smallest products starting with "mo". And so on for each character.

We want the lexicographically smallest matches, not the most popular or most relevant. That requirement is what makes sorting useful. In a sorted array, all products with a common prefix sit next to each other in a contiguous block, already in alphabetical order. Finding that block efficiently is the core of the problem.

Key Constraints:

Intuition

For each prefix of searchWord, scan through all products, collect the ones that start with that prefix, sort them, and take the first 3. This directly mirrors the problem statement and needs no setup.

The wasteful part is the sorting. We re-sort the matching candidates every time a character is typed, even though the relative order of the products never changes between prefixes.

Algorithm

Example Walkthrough

Input:

For each prefix, we filter all products, sort matches, and take top 3:

Code

The bottleneck is re-sorting matches on every keystroke. The next approach sorts the products once upfront, then uses binary search to locate the matching block directly.

Intuition

Sort the products once, and every group of products sharing a prefix becomes a contiguous block. Searching for prefix "mo" reduces to finding where "mo" would be inserted. Everything from that insertion point onward that still starts with "mo" is a match, already in lexicographic order.

Sort once, then for each prefix use binary search to find the starting position. Check up to 3 products from that position. Because the array is sorted, the first 3 matches starting at the insertion point are the lexicographically smallest.

Algorithm

Example Walkthrough

Code

Binary search repeats a full O(log n) search for every character. Since the valid range only shrinks as the prefix grows, the next approach tracks that range with two pointers and narrows it incrementally instead of recomputing it.

Intuition

The matching block on a sorted array can be tracked directly with two pointers instead of relocated by binary search each time. Maintain left and right bounding the range of products that match the current prefix. The full sorted array is in range initially. When character i is typed, advance left past products that are shorter than i + 1 or have the wrong character at position i, and retreat right past products that fail the same test from the other end.

Adding a character to the prefix can only remove products from the range, never add them, so the two pointers only move inward.

Algorithm

Example Walkthrough

Code

The two-pointer method is optimal for a single search word. When the product list is fixed and many different search words are queried against it, a Trie moves the per-character work down to a single pointer hop and precomputes the answer at every node.

Intuition

Insert every product into a Trie keyed by character. At each node, store the three lexicographically smallest products whose path passes through that node. If the products are inserted in sorted order and each node keeps the first three that reach it, the stored list at any node is already the correct answer for the prefix spelled by the path to that node.

Answering a query then becomes a walk down the Trie. Typing character i moves from the current node to its child for that character. The suggestions for the current prefix are the cached list at that child. Once a character has no matching child, every longer prefix also has no match, so the rest of the answer is empty lists.

This trades extra space and a preprocessing pass for query-time cost that no longer depends on the number of products. It pays off when one product list serves many search words.

Algorithm

Example Walkthrough

Products sorted: ["mobile", "moneypot", "monitor", "mouse", "mousepad"], searchWord = "mouse". Inserting in this order fills each node's cached list with the first three products to pass through it.

Walking the query:

Code