1268. Search Suggestions System - Explanation

1. Brute Force

Intuition

For each prefix of the search word, we need to find up to three products that match that prefix in lexicographical order. By sorting products first, we guarantee that the first matching products we encounter are the lexicographically smallest. We then scan through all products for each prefix, collecting up to three matches.

Algorithm

Sort the products array lexicographically.
For each prefix length i from 1 to m (length of searchWord):
- Create an empty list for current suggestions.
- Iterate through all products and check if the first i characters match the current prefix.
- Add matching products to the list until we have 3.
- If no matches are found, fill remaining positions with empty lists and break early.
- Append the current suggestions to the result.
Return the result list.

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []
        m = len(searchWord)
        products.sort()

        for i in range(m):
            cur = []
            for w in products:
                if len(w) <= i:
                    continue

                flag = True
                for j in range(i + 1):
                    if w[j] != searchWord[j]:
                        flag = False
                        break

                if flag:
                    cur.append(w)
                    if len(cur) == 3:
                        break

            if not cur:
                for j in range(i, m):
                    res.append([])
                break
            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * n)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

2. Sorting + Binary Search

Intuition

Once products are sorted, all products sharing a prefix form a contiguous block. Instead of scanning all products for each prefix, we use binary search to find where this block starts. Since the prefix grows character by character, the start position can only move forward, so we keep track of it across iterations.

Algorithm

Sort the products array lexicographically.
Initialize prefix as an empty string and start = 0.
For each character in searchWord:
- Append the character to prefix.
- Use binary search to find the first product >= prefix, starting from start.
- Update start to this position.
- Collect up to 3 products starting from start that have prefix as their prefix.
- Append the collected products to the result.
Return the result list.

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []
        m = len(searchWord)
        products.sort()

        prefix = []
        start = 0

        def binary_search(target, start):
            l, r = start, len(products)
            while l < r:
                mid = l + (r - l) // 2
                if products[mid] >= target:
                    r = mid
                else:
                    l = mid + 1
            return l

        for i in range(m):
            prefix.append(searchWord[i])
            start = binary_search("".join(prefix), start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith("".join(prefix)):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

3. Sorting + Binary Search (Built-In Function)

Intuition

This approach is identical to the previous one, but uses built-in binary search functions provided by the language. Functions like bisect_left in Python or lower_bound in C++ handle the binary search logic, making the code cleaner and less error-prone.

Algorithm

Sort the products array lexicographically.
Initialize prefix as an empty string and start = 0.
For each character in searchWord:
- Append the character to prefix.
- Use the built-in lower bound function to find the first product >= prefix.
- Collect up to 3 products from that position that have prefix as their prefix.
- Append the collected products to the result.
Return the result list.

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []
        m = len(searchWord)
        products.sort()

        prefix = ""
        start = 0
        for i in range(m):
            prefix += searchWord[i]
            start = bisect_left(products, prefix, start)

            cur = []
            for j in range(start, min(start + 3, len(products))):
                if products[j].startswith(prefix):
                    cur.append(products[j])
                else:
                    break

            res.append(cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w * \log N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

4. Sorting + Two Pointers

Intuition

Instead of binary searching for each prefix, we maintain a window [l, r] of valid products. As we process each character of the search word, we shrink the window by moving l forward past products that do not match at position i, and moving r backward past products that do not match. The first up to 3 products in the remaining window are our suggestions.

Algorithm

Sort the products array lexicographically.
Initialize two pointers l = 0 and r = n - 1.
For each index i from 0 to m - 1 (each character in searchWord):
- Move l forward while products[l] is too short or has the wrong character at position i.
- Move r backward while products[r] is too short or has the wrong character at position i.
- Collect up to 3 products from the range [l, r].
- Append the collected products to the result.
Return the result list.

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []
        products.sort()

        l, r = 0, len(products) - 1
        for i in range(len(searchWord)):
            c = searchWord[i]

            while l <= r and (len(products[l]) <= i or products[l][i] != c):
                l += 1
            while l <= r and (len(products[r]) <= i or products[r][i] != c):
                r -= 1

            res.append([])
            remain = r - l + 1
            for j in range(min(3, remain)):
                res[-1].append(products[l + j])

        return res

Time & Space Complexity

Time complexity: $O(n \log n + m * w + N)$
Space complexity:
- $O(n)$ or $O(1)$ space for the sorting algorithm.
- $O(m * w)$ space for the output array.

Where $n$ is the total number of characters in the string array $products$ , $N$ is the size of the array $products$ , $m$ is the length of the string $searchWord$ , and $w$ is the average length of each word in the given string array.

Common Pitfalls

Forgetting to Sort Products First

The problem requires returning suggestions in lexicographical order. A common mistake is attempting to find matches without first sorting the products array. Without sorting, you cannot guarantee that the first three matching products are the lexicographically smallest ones.

Not Handling Short Products Correctly

When checking if a product matches the current prefix, you must verify that the product is long enough to contain the prefix. Accessing product[i] when product.length <= i causes an index out of bounds error. Always check the product length before comparing characters at a given position.

Inefficient Prefix Matching

Rebuilding or recomputing the prefix string from scratch for each character of the search word leads to unnecessary overhead. Instead, incrementally build the prefix by appending one character at a time, and reuse the previous search position since matching products form a contiguous block in the sorted array.