*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #1268 (*Medium*): Search Suggestions System

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given an array of strings

`products`

and a string`searchWord`

. We want to 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 the`searchWord`

. If there are more than three products with a common prefix return the three lexicographically minimums products.Return

list of listsof the suggested`products`

after each character of`searchWord`

is typed.

####
*Examples:*

*Examples:*

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"]]

Example 3: Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags" Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4: Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]

####
*Constraints:*

*Constraints:*

`1 <= products.length <= 1000`

- There are no repeated elements in
`products`

.`1 <= Σ products[i].length <= 2 * 10^4`

- All characters of
`products[i]`

are lower-case English letters.`1 <= searchWord.length <= 1000`

- All characters of
`searchWord`

are lower-case English letters.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Despite the fact that the clues suggest a **binary search** and a **trie**, the optimal solution to this problem needs neither. The substrings formed by adding one letter at a time from the search word (**S**) are naturally already in lexicographical order, as are the results that we're instructed to push into our answer array (**ans**).

So if we sort the products array (**P**), we should only ever need to iterate through **P** once during the entire remaining process of the solution with a **time complexity** of **O(N)**. A single binary search would only require **log(N) time**, but we'd have to perform **M = S.length** binary searches, so in total they would take **O(M * log(N)) time**, compared to the **O(N)** time of a simple iteration.

With constraints of **1000** on both **M** and **N**, the binary search route would max out at a worse time complexity than iteration. Regardless, the sort itself, which is required for both, requires **O(N * log(N))** time already, so neither option can decrease the overall time complexity required.

So in order to only require a single pass through **P**, we should keep track of the current bounds for the range of matches (**left, right**), then we'll iterate through the characters (**c**) of **S**. At each iteration, we'll first want to move **left** forward and **right** back to narrow the range of matches based on the new value of **c**.

Then we can add the next three elements of **P** to our result array (**res**), as long as they fall inside the range **[left, right]**. Once that's done, we can add **res** to **ans** and move to the next iteration.

Once we've finished iterating through **S**, we can **return ans**.

**Time Complexity: O(N * log(N))**where**N**is the length of**P****Space Complexity: O(1)**excluding output space required for**ans**

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var suggestedProducts = function(P, S) {
P.sort()
let ans = [], left = 0, right = P.length - 1
for (let i = 0; i < S.length; i++) {
let c = S.charAt(i), res = []
while (P[left]?.charAt(i) < c) left++
while (P[right]?.charAt(i) > c) right--
for (let j = 0; j < 3 && left + j <= right; j++)
res.push(P[left+j])
ans.push(res)
}
return ans
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def suggestedProducts(self, P: List[str], S: str) -> List[List[str]]:
P.sort()
ans, left, right = [], 0, len(P) - 1
for i in range(len(S)):
c, res = S[i], []
while left <= right and (len(P[left]) == i or P[left][i] < c): left += 1
while left <= right and (len(P[right]) == i or P[right][i] > c): right -= 1
for j in range(3):
if left + j > right: break
else: res.append(P[left+j])
ans.append(res)
return ans
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public List<List<String>> suggestedProducts(String[] P, String S) {
Arrays.sort(P);
List<List<String>> ans = new ArrayList<>();
int left = 0, right = P.length - 1;
for (int i = 0; i < S.length(); i++) {
List<String> res = new ArrayList<>();
char c = S.charAt(i);
while (left <= right && (P[left].length() == i || P[left].charAt(i) < c)) left++;
while (left <= right && (P[right].length() == i || P[right].charAt(i) > c)) right--;
for (int j = 0; j < 3 && left + j <= right; j++)
res.add(P[left+j]);
ans.add(res);
}
return ans;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& P, string S) {
sort(P.begin(), P.end());
vector<vector<string>> ans;
int left = 0, right = P.size() - 1;
for (int i = 0; i < S.length(); i++) {
vector<string> res;
char c = S[i];
while (left <= right && (P[left].length() == i || P[left][i] < c)) left++;
while (left <= right && (P[right].length() == i || P[right][i] > c)) right--;
for (int j = 0; j < 3 && left + j <= right; j++)
res.push_back(P[left+j]);
ans.push_back(res);
}
return ans;
}
};
```

## Discussion (1)

My Java Solution using Trie Data Structure :