LeetCode 1268 - Search Suggestions System

This problem asks us to build a product suggestion system similar to what appears in e commerce search bars. We are give

leetcodemediumarraystringbinary-searchtriesortingheap-(priority-queue)

LeetCode Problem 1268

Difficulty: 🟡 Medium
Topics: Array, String, Binary Search, Trie, Sorting, Heap (Priority Queue)

Solution

LeetCode 1268 - Search Suggestions System

Problem Understanding

This problem asks us to build a product suggestion system similar to what appears in e commerce search bars. We are given two inputs:

  • products, an array of unique product names
  • searchWord, the word the user types character by character

After each character is typed, we must return up to three product names that start with the current prefix. The suggestions must be:

  1. Prefix matches of the currently typed string
  2. Sorted lexicographically
  3. Limited to at most three results

The output is therefore a list where:

  • The first element contains suggestions after typing the first character
  • The second element contains suggestions after typing the first two characters
  • And so on until the entire searchWord is typed

For example, if the search word is "mouse":

  • After typing "m", we return the best matches starting with "m"
  • After typing "mo", we return the best matches starting with "mo"
  • After typing "mou", we narrow the matches further

The constraints are important:

  • Up to 1000 products
  • Total characters across all products are at most 2 * 10^4
  • Search word length can be up to 1000

These limits are not extremely large, but they are large enough that repeatedly scanning every product for every prefix would become inefficient.

The problem guarantees that:

  • All product names are unique
  • All strings contain only lowercase English letters

This simplifies the implementation because we do not need to handle duplicates or special characters.

Several edge cases are important:

  • Only one product exists
  • No products match after some prefix
  • Many products share the same prefix
  • The search word becomes more specific and reduces matches
  • Product names may be much longer than the search word

A naive implementation can easily waste time repeatedly scanning the full product list for every prefix.

Approaches

Brute Force Approach

The simplest solution is to generate every prefix of searchWord and scan the entire products array each time.

For every prefix:

  1. Check every product
  2. Keep products whose names start with the prefix
  3. Sort the matches lexicographically
  4. Take the first three products

This approach is correct because it explicitly evaluates every possible candidate for every prefix.

However, it is inefficient because the same products are repeatedly scanned and sorted for every prefix. If the search word has length m and there are n products, we repeatedly perform expensive prefix checks and sorting operations.

Optimal Approach

The key observation is that lexicographical ordering is extremely useful here.

If we sort the products once at the beginning:

  • Products sharing the same prefix become grouped together
  • The smallest lexicographical products naturally appear first

Then, for each prefix, we can use binary search to locate the first product that could match that prefix.

Because matching products appear consecutively in sorted order, we only need to inspect the next few products after the binary search result. Since we only need at most three suggestions, we check at most three candidates.

This dramatically reduces repeated work.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * log n) O(n) Repeatedly scans and sorts matching products
Optimal O(n log n + m log n) O(1) excluding output Sort once, then use binary search for each prefix

Where:

  • n is the number of products
  • m is the length of searchWord

Algorithm Walkthrough

Optimal Algorithm

  1. Sort the products array lexicographically.

This is the most important preprocessing step. After sorting, all products with the same prefix become contiguous in the array, and the lexicographically smallest products appear first automatically. 2. Initialize an empty result list.

Each entry in this result list will correspond to suggestions after typing one additional character. 3. Build prefixes incrementally.

Start with an empty string. For every character in searchWord, append it to the current prefix.

For example:

  • "m"
  • "mo"
  • "mou"
  • "mous"
  • "mouse"
  1. Use binary search to find the insertion position of the current prefix.

Since the array is sorted, binary search can quickly locate the leftmost position where the prefix could appear.

In Python, this is done with bisect_left.

In Go, we implement the binary search manually using sort.SearchStrings. 5. Collect up to three matching products.

Starting from the binary search index:

  • Check the current product
  • Verify whether it starts with the prefix
  • Add it to the suggestions if it matches
  • Stop after collecting three suggestions

Since matching products are contiguous in sorted order, the first three valid matches are guaranteed to be the correct answer. 6. Append the suggestions list to the final result. 7. Continue until all prefixes are processed.

Why it works

The algorithm works because lexicographical sorting guarantees that all strings sharing the same prefix appear consecutively. Binary search finds the first possible matching position efficiently, and scanning forward retrieves the smallest matching products in sorted order. Since we only need three suggestions, checking a few nearby elements is sufficient.

Python Solution

from bisect import bisect_left
from typing import List

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

        result = []
        prefix = ""

        for char in searchWord:
            prefix += char

            start_index = bisect_left(products, prefix)

            suggestions = []

            for i in range(start_index, min(start_index + 3, len(products))):
                if products[i].startswith(prefix):
                    suggestions.append(products[i])

            result.append(suggestions)

        return result

The implementation begins by sorting the products array. This ensures lexicographical ordering and groups matching prefixes together.

The variable prefix is built incrementally as characters are processed from searchWord. For every new prefix, bisect_left performs binary search to locate the first position where the prefix could appear.

From that index, we inspect at most three products. Since the array is sorted, the first three valid matches are automatically the correct suggestions.

The startswith check is still necessary because binary search only guarantees the insertion position, not that the product actually matches the prefix.

Finally, each suggestion list is appended to the result.

Go Solution

package main

import (
	"sort"
	"strings"
)

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)

	result := [][]string{}
	prefix := ""

	for _, ch := range searchWord {
		prefix += string(ch)

		startIndex := sort.SearchStrings(products, prefix)

		suggestions := []string{}

		for i := startIndex; i < len(products) && i < startIndex+3; i++ {
			if strings.HasPrefix(products[i], prefix) {
				suggestions = append(suggestions, products[i])
			}
		}

		result = append(result, suggestions)
	}

	return result
}

The Go solution follows the same strategy as the Python implementation.

The main difference is that Go does not have a built in bisect_left equivalent, so we use sort.SearchStrings, which performs binary search on a sorted slice.

Prefix checking is done using strings.HasPrefix.

Slices in Go naturally handle dynamic growth when appending suggestions.

Worked Examples

Example 1

Input:

products = ["mobile","mouse","moneypot","monitor","mousepad"]
searchWord = "mouse"

After sorting:

["mobile","moneypot","monitor","mouse","mousepad"]
Prefix Binary Search Position Matching Products Suggestions
"m" 0 all products ["mobile","moneypot","monitor"]
"mo" 0 all products ["mobile","moneypot","monitor"]
"mou" 3 ["mouse","mousepad"] ["mouse","mousepad"]
"mous" 3 ["mouse","mousepad"] ["mouse","mousepad"]
"mouse" 3 ["mouse","mousepad"] ["mouse","mousepad"]

Final output:

[
  ["mobile","moneypot","monitor"],
  ["mobile","moneypot","monitor"],
  ["mouse","mousepad"],
  ["mouse","mousepad"],
  ["mouse","mousepad"]
]

Example 2

Input:

products = ["havana"]
searchWord = "havana"

Sorted products:

["havana"]
Prefix Binary Search Position Suggestions
"h" 0 ["havana"]
"ha" 0 ["havana"]
"hav" 0 ["havana"]
"hava" 0 ["havana"]
"havan" 0 ["havana"]
"havana" 0 ["havana"]

Final output:

[
  ["havana"],
  ["havana"],
  ["havana"],
  ["havana"],
  ["havana"],
  ["havana"]
]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log n) Sorting dominates preprocessing, each prefix uses binary search
Space O(1) excluding output Only a few temporary variables are used

The sorting step costs O(n log n).

For each prefix of length m, binary search takes O(log n). We then inspect at most three products, which is constant time.

Therefore, the total complexity becomes:

O(n log n + m log n)

The algorithm uses only constant extra space aside from the output list.

Test Cases

from typing import List

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        from bisect import bisect_left

        products.sort()

        result = []
        prefix = ""

        for char in searchWord:
            prefix += char

            start_index = bisect_left(products, prefix)

            suggestions = []

            for i in range(start_index, min(start_index + 3, len(products))):
                if products[i].startswith(prefix):
                    suggestions.append(products[i])

            result.append(suggestions)

        return result

solution = Solution()

# Example 1
assert solution.suggestedProducts(
    ["mobile","mouse","moneypot","monitor","mousepad"],
    "mouse"
) == [
    ["mobile","moneypot","monitor"],
    ["mobile","moneypot","monitor"],
    ["mouse","mousepad"],
    ["mouse","mousepad"],
    ["mouse","mousepad"]
]  # standard example with multiple matches

# Example 2
assert solution.suggestedProducts(
    ["havana"],
    "havana"
) == [
    ["havana"],
    ["havana"],
    ["havana"],
    ["havana"],
    ["havana"],
    ["havana"]
]  # single product case

# No matching products after first character
assert solution.suggestedProducts(
    ["apple", "banana", "carrot"],
    "dog"
) == [
    [],
    [],
    []
]  # no matches at all

# Products sharing long prefixes
assert solution.suggestedProducts(
    ["app", "apple", "application", "apply"],
    "app"
) == [
    ["app", "apple", "application"],
    ["app", "apple", "application"],
    ["app", "apple", "application"]
]  # verifies lexicographical ordering

# Fewer than three matches
assert solution.suggestedProducts(
    ["bags", "baggage", "banner"],
    "bags"
) == [
    ["baggage", "bags", "banner"],
    ["baggage", "bags"],
    ["bags"],
    ["bags"]
]  # shrinking result set

# Exact match only
assert solution.suggestedProducts(
    ["cat", "dog", "fish"],
    "cat"
) == [
    ["cat"],
    ["cat"],
    ["cat"]
]  # exact single match

# Prefix becomes invalid midway
assert solution.suggestedProducts(
    ["hello", "help", "helmet"],
    "hex"
) == [
    ["hello", "helmet", "help"],
    ["hello", "helmet", "help"],
    []
]  # valid early prefixes but invalid later

Test Summary

Test Why
Standard mouse example Verifies core functionality
Single product Ensures repeated matching works
No matches Verifies empty suggestion handling
Shared prefixes Tests lexicographical ordering
Fewer than three matches Ensures partial suggestion lists work
Exact match Confirms exact prefix behavior
Prefix becomes invalid Tests transition from valid to empty results

Edge Cases

No Matching Products

A common bug occurs when no products match a prefix. Some implementations may continue scanning unnecessarily or accidentally include unrelated products.

For example:

products = ["apple", "banana"]
searchWord = "cat"

Binary search locates the insertion position, but the startswith check prevents unrelated products from being added. The implementation correctly returns empty lists for all prefixes.

Fewer Than Three Suggestions

The problem requires returning at most three suggestions, not exactly three.

For example:

products = ["mouse", "mousepad"]
searchWord = "mouse"

Only two matching products exist. The algorithm naturally stops when it reaches the array boundary or runs out of matching products.

Prefix Stops Matching Midway

Another tricky case occurs when early prefixes match but later prefixes do not.

For example:

products = ["hello", "help", "helmet"]
searchWord = "hex"

The prefixes "h" and "he" match several products, but "hex" matches none.

The implementation handles this correctly because every prefix performs a fresh binary search and validates matches independently.

Lexicographical Ordering

A naive implementation might collect matching products in original input order instead of lexicographical order.

Sorting the array once at the beginning guarantees that the first matching products encountered are always the lexicographically smallest valid suggestions.