Search Suggestions System

Given a list of products and a searchWord, for each character typed in searchWord return up to 3 lexicographically smallest product suggestions starting with that prefix.

Example 1

Input: products=["mobile","mouse","moneypot","monitor","mousepad"], searchWord="mouse" → Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Solution Approach

Sort products. For each prefix, binary search to find the first matching product, then take up to 3 products starting with that prefix.

Sort products.
For each prefix (length 1..n): binary search for first product >= prefix.
Collect up to 3 products that start with the current prefix.

Java

import java.util.*;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        String prefix = "";
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            int idx = Arrays.binarySearch(products, prefix);
            if (idx < 0) idx = -idx - 1;
            List<String> suggestions = new ArrayList<>();
            for (int i = idx; i < Math.min(idx+3, products.length); i++) {
                if (products[i].startsWith(prefix)) suggestions.add(products[i]);
                else break;
            }
            result.add(suggestions);
        }
        return result;
    }
}

Time Complexity: O(N log N + L log N) where L=searchWord length
Space Complexity: O(N) for sorting