# Search Suggestions System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/search-suggestions-system)
Canonical: https://scaleengineer.com/dsa/problems/search-suggestions-system
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, String, Trie, Heap (Priority Queue)
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Wix](https://scaleengineer.com/companies/wix), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Anduril](https://scaleengineer.com/companies/anduril), [UBS](https://scaleengineer.com/companies/ubs), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Coursera](https://scaleengineer.com/companies/coursera), [Deliveroo](https://scaleengineer.com/companies/deliveroo)
---
## Problem
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 common prefix with `searchWord`. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return _a list of lists of the suggested products after each character of_ `searchWord` _is typed_.

**Example 1:**

**Input:** products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
**Output:** [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
**Explanation:** products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

**Example 2:**

**Input:** products = ["havana"], searchWord = "havana"
**Output:** [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
**Explanation:** The only word "havana" will be always suggested while typing the search word.

**Constraints:**

* `1 <= products.length <= 1000`
* `1 <= products[i].length <= 3000`
* `1 <= sum(products[i].length) <= 2 * 104`
* All the strings of `products` are **unique**.
* `products[i]` consists of lowercase English letters.
* `1 <= searchWord.length <= 1000`
* `searchWord` consists of lowercase English letters.

# Approaches
## Brute Force Iteration
This approach simulates the process directly. For each character typed, it forms the current prefix. It then iterates through the entire list of products, collecting all products that start with this prefix. Finally, it sorts the collected matches and picks the top three.
**Time:** O(M * (N*L + N log N * L)), where `M` is the length of `searchWord`, `N` is the number of products, and `L` is the maximum length of a product. For each of the `M` prefixes, we iterate through `N` products (`O(N)`), each `startsWith` check takes up to `O(L)` time, and sorting `N` products takes `O(N log N * L)`. This is highly inefficient. · **Space:** O(N * L), where N is the number of products and L is their maximum length. This space is required to store the matching products for each prefix before sorting and trimming.
**Pros:** Simple to understand and implement.
**Cons:** Very slow, especially for long search words and large product lists.; It recomputes and re-sorts for every single character typed, leading to a lot of redundant work.
### Explanation
We iterate from the first character of `searchWord` up to its full length.
In each iteration `i`, we consider the prefix `p = searchWord.substring(0, i+1)`.
We create a temporary list, `matches`.
We loop through every `product` in the `products` array.
For each `product`, we check if it `startsWith(p)`. If it does, we add it to `matches`.
After checking all products, we sort the `matches` list lexicographically.
We then take the first 3 elements from the sorted `matches` list (or all of them if there are fewer than 3) and add this sublist to our final result.
This process is repeated for all prefixes of `searchWord`.

```java
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> result = new ArrayList<>();
        StringBuilder prefix = new StringBuilder();
        for (char c : searchWord.toCharArray()) {
            prefix.append(c);
            List<String> matches = new ArrayList<>();
            for (String product : products) {
                if (product.startsWith(prefix.toString())) {
                    matches.add(product);
                }
            }
            Collections.sort(matches);
            List<String> suggestions = new ArrayList<>();
            for (int i = 0; i < Math.min(3, matches.size()); i++) {
                suggestions.add(matches.get(i));
            }
            result.add(suggestions);
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list of lists `result`.
- Initialize an empty string `prefix`.
- Iterate through each character `c` of `searchWord`:
  - Append `c` to `prefix`.
  - Create an empty list `suggestions`.
  - Iterate through each `product` in the `products` array:
    - If `product` starts with `prefix`, add `product` to `suggestions`.
  - Sort `suggestions` lexicographically.
  - Create a new list `currentResult`.
  - Add the first `min(3, suggestions.size())` elements from `suggestions` to `currentResult`.
  - Add `currentResult` to `result`.
- Return `result`.

## Sorting and Binary Search
This approach improves upon the brute-force method by pre-sorting the `products` array. Once sorted, all products with a common prefix will be grouped together. For each prefix, we can use binary search to quickly find the starting point of this group.
**Time:** O(N log N * L + M * L * log N). Sorting takes `O(N log N * L)`. For each of the `M` prefixes, binary search takes `O(log N)` comparisons, and each string comparison takes up to `O(L)` time. · **Space:** O(L) for storing the prefix, plus the space for sorting (typically `O(log N)` or `O(N)` depending on implementation) and the output list.
**Pros:** Much faster than brute force due to pre-sorting and efficient searching with binary search.
**Cons:** Performs a separate binary search for each prefix, which involves some redundant work.
### Explanation
First, we sort the `products` array lexicographically. This is a one-time operation.
We then iterate through each character of `searchWord` to form prefixes, one by one.
For each prefix, we use binary search (like a custom `lower_bound` function) to find the insertion point of this prefix in the sorted `products` array. This index, let's call it `start`, is where the block of matching products begins.
Starting from `start`, we iterate through the `products` array. We check the next few products to see if they actually start with the current prefix.
We collect up to three such matching products. Since the array is sorted, these will be the lexicographically smallest ones.
We can stop checking as soon as we find a product that doesn't start with the prefix, or once we have collected three suggestions.

```java
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        StringBuilder prefix = new StringBuilder();
        for (char c : searchWord.toCharArray()) {
            prefix.append(c);
            int start = findLowerBound(products, prefix.toString());
            List<String> suggestions = new ArrayList<>();
            for (int i = start; i < Math.min(start + 3, products.length); i++) {
                if (products[i].startsWith(prefix.toString())) {
                    suggestions.add(products[i]);
                }
            }
            result.add(suggestions);
        }
        return result;
    }

    // Custom binary search to find the first element >= target
    private int findLowerBound(String[] products, String target) {
        int low = 0, high = products.length;
        int ans = products.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (products[mid].compareTo(target) >= 0) {
                ans = mid;
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
- Sort the `products` array lexicographically using `Arrays.sort(products)`.
- Initialize an empty list of lists `result`.
- Build a `prefix` string character by character from `searchWord`.
- For each `prefix`:
  - Use binary search to find the index `start` of the first word in `products` that is greater than or equal to the `prefix`.
  - Initialize an empty list `suggestions`.
  - Iterate from `start` for up to 3 elements or until the end of the array.
  - If `products[i]` starts with the `prefix`, add it to `suggestions`.
  - Add the `suggestions` list to the `result`.
- Return `result`.

## Trie (Prefix Tree)
A Trie is a tree-like data structure that is ideal for prefix-based searches. We can build a Trie from the `products` list and store suggestions at each node. This allows for very fast lookups once the Trie is constructed.
**Time:** O(N log N * L + S), where `S` is the total number of characters in all products. Sorting takes `O(N log N * L)`. Building the Trie takes `O(S)`. Searching takes `O(M)`. The overall complexity is dominated by the preprocessing steps. · **Space:** O(S), where `S` is the total number of characters in all products. The number of nodes in the Trie is at most `S`. Each node stores pointers to children and a small list of suggestions (pointers to strings), so the space is proportional to `S`.
**Pros:** Extremely fast search time (`O(M)`).; A good choice if the product list is static and queried many times.
**Cons:** Higher space complexity compared to the two-pointer approach.; The preprocessing time (sorting and building the Trie) can be significant.
### Explanation
To optimize, we first sort the `products` array lexicographically.
We define a `TrieNode` class, where each node contains an array of children (for each letter 'a'-'z') and a list to store suggestions.
We build the Trie by inserting every product from the sorted list. As we traverse the Trie for a product, we add that product to the suggestion list of each node on the path, but only if the list has fewer than 3 items. Since we insert products in lexicographical order, the first three products encountered for any prefix path will be the smallest ones.
After building the Trie, we search for suggestions. We traverse the Trie character by character according to `searchWord`.
For each character, we move to the corresponding child node. We then add the suggestion list from that node to our result.
If at any point a character does not have a corresponding child node, it means no products match from that point on. We then fill the rest of the results with empty lists.

```java
class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        List<String> suggestions = new ArrayList<>();
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        TrieNode root = new TrieNode();
        
        // Build Trie
        for (String p : products) {
            TrieNode node = root;
            for (char c : p.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
                if (node.suggestions.size() < 3) {
                    node.suggestions.add(p);
                }
            }
        }
        
        // Search
        List<List<String>> result = new ArrayList<>();
        TrieNode node = root;
        for (char c : searchWord.toCharArray()) {
            if (node != null) {
                node = node.children[c - 'a'];
            }
            if (node == null) {
                result.add(new ArrayList<>());
            } else {
                result.add(node.suggestions);
            }
        }
        return result;
    }
}
```
### Algorithm
- Sort the `products` array lexicographically.
- Create a `Trie` with a root `TrieNode`. Each node should contain children pointers and a list for suggestions.
- For each `product` in the sorted `products` array:
  - Insert the `product` into the Trie. At each `TrieNode` along the insertion path, if `node.suggestions.size() < 3`, add the `product` to `node.suggestions`.
- Initialize an empty list of lists `result`.
- Traverse the Trie using characters from `searchWord`, starting from the root.
- For each character, move to the corresponding child node.
- If the path exists, add the suggestions from the current node to the `result`. Otherwise, add an empty list.
- Continue until all characters of `searchWord` are processed.
- Return `result`.

## Sorting with Two Pointers
This is the most efficient approach in terms of both time and space. It starts by sorting the `products` array. Then, instead of re-searching from scratch for each prefix, it maintains a `left` and `right` pointer to narrow down the range of matching products as the prefix gets longer.
**Time:** O(N log N * L + M + N). Sorting takes `O(N log N * L)`. The two pointers `left` and `right` traverse the array at most once in total across all iterations of the main loop, which takes `O(N)` character comparisons. The outer loop runs `M` times. So the search part is `O(M + N)`. The total time is dominated by sorting. · **Space:** O(log N) or O(N) for the in-place sort, depending on the language's implementation. This is very space-efficient.
**Pros:** Optimal time complexity and very low space complexity.; Generally the best all-around solution for this problem.
**Cons:** The initial sorting cost might be high if the number of products is very large, but it's generally necessary for finding the lexicographically smallest results efficiently.
### Explanation
First, sort the `products` array lexicographically.
Initialize two pointers, `left = 0` and `right = products.length - 1`. These pointers will define the window of products that are candidates for the current prefix.
Iterate through the `searchWord` character by character (from index `i = 0` to `M-1`).
In each iteration, shrink the window `[left, right]`:
- Move `left` forward as long as `products[left]` does not match the prefix up to character `i`. A product doesn't match if it's too short (length `< i+1`) or if the character at index `i` is different from the `i`-th character of `searchWord`.
- Similarly, move `right` backward as long as `products[right]` does not match the prefix.
After adjusting the pointers, all products between `left` and `right` (inclusive) are guaranteed to have the current prefix.
The first three products in this range (`products[left]`, `products[left+1]`, ...) are the desired suggestions. We add up to three of these to our result list for the current prefix. The number of suggestions will be `min(3, right - left + 1)`.

```java
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        int left = 0;
        int right = products.length - 1;
        
        for (int i = 0; i < searchWord.length(); i++) {
            char c = searchWord.charAt(i);
            
            // Move left pointer
            while (left <= right && (products[left].length() <= i || products[left].charAt(i) != c)) {
                left++;
            }
            
            // Move right pointer
            while (left <= right && (products[right].length() <= i || products[right].charAt(i) != c)) {
                right--;
            }
            
            List<String> suggestions = new ArrayList<>();
            if (left <= right) {
                int count = Math.min(3, right - left + 1);
                for (int j = 0; j < count; j++) {
                    suggestions.add(products[left + j]);
                }
            }
            result.add(suggestions);
        }
        
        return result;
    }
}
```
### Algorithm
- Sort the `products` array lexicographically.
- Initialize two pointers, `left = 0` and `right = products.length - 1`.
- Iterate through `searchWord` with index `i`.
  - Get the character `c = searchWord.charAt(i)`.
  - Move `left` pointer forward while `left <= right` and `products[left]` does not match the prefix up to `i`.
  - Move `right` pointer backward while `left <= right` and `products[right]` does not match the prefix up to `i`.
  - The products in the range `[left, right]` now match the current prefix.
  - Add up to the first 3 products from this range to the current list of suggestions.
  - Add the suggestions to the final result list.
- Return the result.

# Solutions
### Java

```java
class Trie { Trie [] children = new Trie [ 26 ]; List < Integer > v = new ArrayList <>(); public void insert ( String w , int i ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; if ( node . v . size () < 3 ) { node . v . add ( i ); } } } public List < Integer >[] search ( String w ) { Trie node = this ; int n = w . length (); List < Integer >[] ans = new List [ n ]; Arrays . setAll ( ans , k -> new ArrayList <>()); for ( int i = 0 ; i < n ; ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { break ; } node = node . children [ idx ]; ans [ i ] = node . v ; } return ans ; } } class Solution { public List < List < String >> suggestedProducts ( String [] products , String searchWord ) { Arrays . sort ( products ); Trie trie = new Trie (); for ( int i = 0 ; i < products . length ; ++ i ) { trie . insert ( products [ i ], i ); } List < List < String >> ans = new ArrayList <>(); for ( var v : trie . search ( searchWord )) { List < String > t = new ArrayList <>(); for ( int i : v ) { t . add ( products [ i ]); } ans . add ( t ); } return ans ; } }
```

### CPP

```cpp
class Trie { public: void insert ( string & w , int i ) { Trie * node = this ; for ( int j = 0 ; j < w . size (); ++ j ) { int idx = w [ j ] - 'a' ; if ( ! node -> children [ idx ]) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; if ( node -> v . size () < 3 ) { node -> v . push_back ( i ); } } } vector < vector < int >> search ( string & w ) { Trie * node = this ; int n = w . size (); vector < vector < int >> ans ( n ); for ( int i = 0 ; i < w . size (); ++ i ) { int idx = w [ i ] - 'a' ; if ( ! node -> children [ idx ]) { break ; } node = node -> children [ idx ]; ans [ i ] = move ( node -> v ); } return ans ; } private: vector < Trie *> children = vector < Trie *> ( 26 ); vector < int > v ; }; class Solution { public: vector < vector < string >> suggestedProducts ( vector < string >& products , string searchWord ) { sort ( products . begin (), products . end ()); Trie * trie = new Trie (); for ( int i = 0 ; i < products . size (); ++ i ) { trie -> insert ( products [ i ], i ); } vector < vector < string >> ans ; for ( auto & v : trie -> search ( searchWord )) { vector < string > t ; for ( int i : v ) { t . push_back ( products [ i ]); } ans . push_back ( move ( t )); } return ans ; } };
```

### Python

```python
class Trie : def __init__ ( self ): self . children : List [ Union [ Trie , None ]] = [ None ] * 26 self . v : List [ int ] = [] def insert ( self , w , i ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] if len ( node . v ) < 3 : node . v . append ( i ) def search ( self , w ): node = self ans = [[] for _ in range ( len ( w ))] for i , c in enumerate ( w ): idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : break node = node . children [ idx ] ans [ i ] = node . v return ans class Solution : def suggestedProducts ( self , products : List [ str ], searchWord : str ) -> List [ List [ str ]]: products . sort () trie = Trie () for i , w in enumerate ( products ): trie . insert ( w , i ) return [[ products [ i ] for i in v ] for v in trie . search ( searchWord )]
```