1268. Search Suggestions System

Quick Identifier

• Topic: tries
• Pattern: Trie (alternative: sort + binary search on products)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Medium
• LeetCode: 1268

Quick Sights

• Time Complexity: a..z from the optimal approach.
• Space Complexity: O(total chars) from the optimal approach.
• Core Mechanism: Given an array products and a searchWord, after typing each successive character of searchWord (prefix after prefix), return up to three lexicographically smallest product names that start with the current prefix.

Concept Explanation

Given an array products and a searchWord, after typing each successive character of searchWord (prefix after prefix), return up to three lexicographically smallest product names that start with the current prefix.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Prefix completion as user types
• Lexicographic order + limit 3 → DFS/BFS on trie with early exit, or sorted array + lower-bound scan
• Sorting products once simplifies both trie DFS order and two-pointer approaches

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — each prefix filter-sort all products — O(P² · log P) over typing steps—too slow at scale.
• Better — sort products once; each prefix take first three strings.HasPrefix scans — O(n log n + output) fine for many LC constraints.
• Optimal (structured) — trie built from sorted products; DFS from prefix node in a..z order collecting ≤3 words — O(total chars) build, O(3 · L) per query layer.

Optimal Solution

Go

package main

import "sort"

type Trie struct {
	children [26]*Trie
	word     string
}

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)
	trie := &Trie{}
	for _, product := range products {
		node := trie
		for index := range product {
			offset := int(product[index] - 'a')
			if node.children[offset] == nil {
				node.children[offset] = &Trie{}
			}
			node = node.children[offset]
		}
		node.word = product
	}
	result := make([][]string, 0, len(searchWord))
	node := trie
	for index := range searchWord {
		offset := int(searchWord[index] - 'a')
		if node == nil || node.children[offset] == nil {
			node = nil
			result = append(result, []string{})
			continue
		}
		node = node.children[offset]
		suggestions := []string{}
		var collect func(*Trie)
		collect = func(current *Trie) {
			if len(suggestions) == 3 {
				return
			}
			if current.word != "" {
				suggestions = append(suggestions, current.word)
				if len(suggestions) == 3 {
					return
				}
			}
			for letterIndex := 0; letterIndex < 26; letterIndex++ {
				child := current.children[letterIndex]
				if child != nil {
					collect(child)
					if len(suggestions) == 3 {
						return
					}
				}
			}
		}
		collect(node)
		result = append(result, suggestions)
	}
	return result
}

JavaScript

class Trie {
	constructor() {
		this.children = new Map();
		this.word = '';
	}
}

function suggestedProducts(products, searchWord) {
	const sorted = [...products].sort();
	const root = new Trie();
	for (const product of sorted) {
		let node = root;
		for (let index = 0; index < product.length; index++) {
			const letter = product[index];
			if (!node.children.has(letter)) {
				node.children.set(letter, new Trie());
			}
			node = node.children.get(letter);
		}
		node.word = product;
	}
	const result = [];
	let node = root;
	for (let index = 0; index < searchWord.length; index++) {
		const letter = searchWord[index];
		if (node === null || !node.children.has(letter)) {
			node = null;
			result.push([]);
			continue;
		}
		node = node.children.get(letter);
		const suggestions = [];
		const collect = (current) => {
			if (suggestions.length === 3) {
				return;
			}
			if (current.word !== '') {
				suggestions.push(current.word);
				if (suggestions.length === 3) {
					return;
				}
			}
			const letters = [...current.children.keys()].sort();
			for (const nextLetter of letters) {
				collect(current.children.get(nextLetter));
				if (suggestions.length === 3) {
					return;
				}
			}
		};
		collect(node);
		result.push(suggestions);
	}
	return result;
}

Walkthrough

products = ["mobile","mouse","moneypot","monitor"], searchWord = "mouse" — sort first → ["mobile","moneypot","monitor","mouse"].

Invariant: once products are lex-sorted, trie DFS in ascending edge order lists completions lexicographically; stop at three items.

Edge Cases

• Prefix impossible → empty arrays for that step and all following (handled by node == nil chaining)
• Fewer than three products with prefix → return all available

Pitfalls

• Not sorting products before naive trie insert—DFS order may not match lex order of completions
• Collecting internal prefixes as words—only terminal nodes should contribute full product strings

Similar Problems

• 208. Implement Trie — core trie mechanics.
• 648. Replace Words — prefix walks on a trie.
• 211. Design Add and Search Words Data Structure — richer matching, same structural ideas.

Variants

• Return more than three suggestions or rank by popularity instead of lex order.
• Streaming catalog updates between keystrokes—dynamic trie maintenance.

Mind-Map Tags

#trie #autocomplete #lex-order #prefix-search #dfs-limit