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.

The key observation is that we want the lexicographically smallest matches, not the most popular or most relevant. This is different from the "Design Search Autocomplete System" problem. Because we want lexicographic order, sorting the products upfront gives us a huge advantage. In a sorted array, all products with a common prefix sit next to each other in a contiguous block. Finding that block efficiently is the core challenge.

Key Constraints:

Intuition

The most natural first attempt: for each prefix, scan through all products, collect the ones that start with that prefix, sort them, and grab the first 3. We already know the products and the prefixes (each prefix of searchWord), so this is straightforward.

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

Algorithm

Example Walkthrough

Input:

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

Code

The bottleneck is re-sorting matching products on every keystroke, even though the products never change order. What if we sorted once upfront and used binary search to find the matching range?

Intuition

Here is the key insight: if we sort the products array once, all products sharing a prefix will be grouped together in a contiguous block. Searching for prefix "mo" means finding where "mo" would be inserted. Everything from that insertion point onward that still starts with "mo" is a match, and they are already in lexicographic order.

So the plan is simple. Sort once, then for each prefix use binary search to find the starting position. Check up to 3 products from that position to see if they match the prefix. Because the array is sorted, the first 3 matches we find are guaranteed to be the lexicographically smallest.

Algorithm

Example Walkthrough

Code

The binary search approach works well, but we compute a new binary search for every character typed. Since the valid range can only shrink as the prefix grows, what if we tracked the range and narrowed it incrementally?

Intuition

Building on the sorted array idea, here is an even cleaner approach. Instead of binary searching every time, we maintain two pointers, left and right, that define the range of products matching the current prefix. Initially, the entire sorted array is in range. As each character is typed, we shrink the range from both ends: move left forward past products that are too short or don't have the right character at the current position, and move right backward past products that don't match either.

This works because adding a character to the prefix can only eliminate products, never add new ones. So the range monotonically shrinks. Each pointer moves at most n total positions across all characters, giving us O(n) total pointer movement.

Algorithm

Example Walkthrough

Code