1268. Search Suggestions System

At a Glance

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

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

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

typed	prefix	first ≤3 matches
`m`	`m`	`mobile`, `moneypot`, `monitor`
`mo`	`mo`	`mobile`, `moneypot`, `monitor`
…	`mou`	narrows toward `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

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