#1268 - Search Suggestions System

MediumTrie

Given an array of products and a searchWord, after each character of searchWord is typed, return a list of at most 3 product suggestions that have the typed prefix. Suggestions should be lexicographically sorted.

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

Solution Space

Try it

/**
 * Returns up to 3 lexicographically smallest product suggestions
 * for each prefix of searchWord.
 *
 * @param products   Array of product names
 * @param searchWord The word being typed character by character
 * @returns          2D array of suggestions per prefix
 */
export function suggestedProducts(
  products: string[],
  searchWord: string,
): string[][] {
  products.sort();
  const result: string[][] = [];

  let lo = 0;
  let hi = products.length - 1;

  for (let i = 0; i < searchWord.length; i++) {
    const ch = searchWord[i];

    // Narrow the window to products matching the current prefix
    while (lo <= hi && (products[lo].length <= i || products[lo][i] !== ch)) {
      lo++;
    }
    while (lo <= hi && (products[hi].length <= i || products[hi][i] !== ch)) {
      hi--;
    }

    const suggestions: string[] = [];
    for (let j = lo; j <= Math.min(lo + 2, hi); j++) {
      suggestions.push(products[j]);
    }
    result.push(suggestions);
  }

  return result;
}

Approach: sort + two-pointer narrowing – sort products lexicographically, then for each typed character narrow the `[lo, hi]` window to products matching the growing prefix. Take the first 3 from the window.

Time: O(m log m + n) – sorting m products; `lo` only increases and `hi` only decreases across all n characters, so total narrowing is O(m), dominated by the sort.

Space: O(1) extra – besides the output and sort.

Alternative approaches:

Approach	Idea	Time	Space
Trie	Build a trie from products, then for each prefix walk the trie and DFS-collect up to 3 lexicographic results	O(T + n · 3) where T = total chars	O(T)

Why the sort + two-pointer approach is preferred: simpler to implement, no extra trie structure, and the two-pointer narrowing is very efficient on sorted data.

#208 Implement Trie (Prefix Tree)

#435 Non-overlapping Intervals