The whole problem is prefix matching: each new character narrows the question to “which words start with this prefix?”, and you are asked for the three smallest such words after every character. There are two honest ways to answer that question quickly, and both lean on the same trick — sort the product list once. Once the column is sorted, every match for a prefix lives in one contiguous block, because words sharing a prefix are never separated by words that do not share it. Finding that block is a binary search, not a scan; “the three smallest” is then just “the first three words of the block”. The brute approach skips the block insight and rescan-filter the whole column for every prefix; the optimal approach locates each block directly.
Brute Force: Filter Every Prefix
Time O(S·L)Space O(S)Ignore the ordering insight and answer each prefix by scanning the whole column. Sort the products once (so [:3] is meaningful), then for each of the L typed prefixes build a fresh match list by testing every word with startswith, and keep the first three matches.
class Solution: def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]: products.sort() ans = [] for i in range(1, len(searchWord) + 1): prefix = searchWord[:i] match = [p for p in products if p.startswith(prefix)] ans.append(match[:3]) return ansWhy it is slow: each of the L characters triggers a full O(S) pass over the column, so the work is O(S·L) on top of the one-time sort. As prefixes grow, the matches shrink — yet the brute pass still reads every word that stopped matching characters ago, which is exactly the redundant work the block view removes.
Sorted Window with Binary Search
OptimalTime O(S log S + L log S)Space O(S)Sort the column once, then answer every prefix without rescanning. A prefix is just a string, and the sorted column is sorted strings — so bisect_left(products, prefix) returns the first index whose word is at least prefix, which is the start of the matching block. The block ends where words no longer share the prefix; because all letters are lowercase, "prefix" + "{" (the character right after 'z') sorts after every word that starts with prefix and before every word that does not, so a second bisect_left gives the block end. The answer is that block sliced to its first three words.
from bisect import bisect_left
class Solution: def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]: products.sort() ans = [] for i in range(1, len(searchWord) + 1): prefix = searchWord[:i] # One binary search for the block start, one for the block end. low = bisect_left(products, prefix) high = bisect_left(products, prefix + "{") # "{" sorts right after "z" ans.append(products[low:high][:3]) return ansTrace the file example, products = ["mobile","mouse","moneypot","monitor","mousepad"] and searchWord = "mouse" — watch the matched block light up amber and shrink, then turn its first three words green:
Sorted products (the working column)
Typed prefix
Sort the product names once, then keep them as the working column. Every later question is the same shape: given a growing prefix, show the three smallest words that start with it. Because the column is sorted, the answers to every prefix sit together in one contiguous block, so each prefix is answered by finding that block, not by rescanning all five names.
Why it is efficient: the sort costs O(S log S) once, and each of the L prefixes is answered by two binary searches of O(log S) — the whole search is O(S log S + L log S), a large win over the O(S·L) brute pass. The trick of the search is the sentinel character: "{" sits just past all lowercase letters, so bisect_left(products, prefix + "{") is a clean block end with no manual prefix check. A trie is an alternative that stores the top three tips per node and reaches O(total product length) build time, at the cost of more code and O(total length) space; the sorted column keeps it simpler with the same asymptotic behavior for this input size.