Abstract / Summary

Given a list of search queries, suggest up to three popular queries for each prefix after typing each character.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Heap (Priority Queue)
• Sorting
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The suggestedProducts method receives a list of product names and a search word, then returns a two-dimensional vector where each inner vector contains up to three lexicographically smallest products that share the current prefix of the search word. The implementation relies on sorting the product list once and performing a binary search for each incremental prefix, extracting at most three matching entries.

Key Steps

Sorting the product list

sort(products.begin(), products.end());

Sorting establishes a deterministic order that enables binary search and guarantees that the first three matches encountered are the smallest lexicographically.

Incrementally building the prefix

string lookFor;
for (auto i : searchWord)
{
    lookFor += i;
    // ...
}

A running string lookFor accumulates one character per iteration, representing the current prefix of searchWord. This incremental approach avoids recomputing the prefix from scratch on each loop.

Binary search for the lower bound

auto pos = lower_bound(products.begin(), products.end(), lookFor);

lower_bound locates the first element that is not less than the current prefix. Because the vector is sorted, this operation jumps directly to the region where matching products may begin, skipping all earlier entries.

Collecting up to three suggestions

vector<string> three;
while (pos != products.end() && three.size() < 3)
{
    auto next = *pos++;
    if (next.find(lookFor) != 0)
        break;
    three.push_back(next);
}
result.push_back(three);

A loop walks forward from the lower-bound position, checking each candidate with find. The condition next.find(lookFor) != 0 verifies that the candidate starts with the prefix; a mismatch triggers an early exit. The loop stops after three valid entries have been gathered, ensuring the result size never exceeds the required limit.

Edge Cases Handled

When the input products vector is empty, the initial sort is a no-op and each iteration of the prefix loop yields an empty three vector, which is still appended to result. If searchWord itself is empty, the outer loop never executes, and the method returns an empty outer vector, matching the expectation of no prefixes to suggest.

If a particular prefix does not exist in any product, lower_bound points to the first element greater than the prefix. The subsequent while loop immediately encounters a mismatch (find returns a non-zero position) and breaks, resulting in an empty inner vector for that prefix.

When fewer than three products share a prefix, the while condition three.size() < 3 naturally limits the loop, and the method returns only the available matches without attempting to access non-existent elements.

Performance Optimizations

The algorithm performs a single global sort, which costs (O(n \log n)) but is incurred only once regardless of the length of searchWord. For each character added to the prefix, a binary search (lower_bound) runs in logarithmic time, quickly narrowing the search window.

The forward scan after the lower bound stops as soon as a non-matching product is found, preventing unnecessary traversal of the remainder of the vector. Limiting the collection to three entries caps the work per prefix, ensuring that even in the worst case the inner loop executes at most three iterations.

By reusing the same lookFor string and extending it in place, the code avoids repeated allocation of temporary substrings, reducing overhead associated with string construction. The combination of sorted data, binary search, early termination, and a fixed-size result buffer yields an efficient solution for generating incremental product suggestions.

Imagine you have a big box of toy labels and you want to find the best ones to show a friend while you type out a secret word one letter at a time. First, the computer acts like a helpful librarian who organizes all the labels in the box in alphabetical order so they are easy to look through.

Next, the computer looks at the first letter of the secret word. It skips over all the labels that do not start with that letter and picks out the first three labels it finds that match. It puts those three into a special container.

Then, the computer looks at the first two letters of the word together. It does the same thing, searching through the organized labels to see if any of them start with those two letters. It gathers a few more labels that fit and adds them to another container.

The computer does this over and over again, adding one more letter from the word each time. At every step, it searches the organized pile to find matching labels and carefully places up to three of them into their own little group. By the time it finishes typing every letter of the secret word, it has collected a whole list of groups, where each group shows the best matching labels for that part of the word.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	varunu28				Java
	wisdompeak	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality