Skip to main content

1268. Search Suggestions System

medium

After each character of a search query, return the top 3 lexicographic product matches with that prefix. The classic 'sort + binary search' alternative to a trie — interviewers love comparing the two.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 smallest products. Return a list of lists of the suggested products after each character of searchWord is typed.

Constraints

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

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

Example 2

Input
products = ["havana"], searchWord = "havana"
Output
[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort products lexicographically. After sorting, every set of strings sharing a prefix is contiguous.

Hint 2

For each prefix length, use lower_bound binary search to find the leftmost product >= prefix.

Hint 3

Take up to 3 products starting at that position, but only include those that still start with the prefix.

Solution approach

Reveal approach

Sort products lexicographically first — once sorted, every prefix-matching block is a contiguous range. For each prefix p of searchWord (lengths 1 through |searchWord|), use lower_bound binary search to find the leftmost index i where products[i] >= p. Then take up to three entries products[i], products[i + 1], products[i + 2], including each only if it starts with p. The starts-with check is what filters out products that sort after p but don't share the prefix. Sorting costs O(L log n) where L is the average string length. Each query is O(log n) for the binary search plus O(1) for the slice. Total: O(n L log n + Q log n) where Q = |searchWord|. A trie achieves the same asymptotic but the sort + binary-search version uses dramatically less memory and is faster to write in an interview.

Complexity

Time
O(n L log n + Q log n)
Space
O(1) extra (sort in place)

Related patterns

  • binary-search
  • string
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Search Suggestions System and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →