TL;DR
Sort once, then binary search each prefix with bisect_left — O((T + L·n) after an O(n log n · L) sort, effectively O(n·L log n)) time, O(1) extra space (excluding output).
Approach 1 — Brute force
Sort the products so lexicographic order is free. Then for each prefix of searchWord, scan the entire list and keep the first three products that start with the prefix.
from typing import List
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
result: List[List[str]] = []
prefix = ""
for ch in searchWord:
prefix += ch
matches: List[str] = []
for p in products:
if p.startswith(prefix):
matches.append(p)
if len(matches) == 3:
break
result.append(matches)
return result
- Time: O(n log n · L) for the sort plus O(m · n · L) for the scans, where
n = len(products), m = len(searchWord), L = max product length.
- Space: O(1) beyond the output.
With n = 1000 and m = 1000 this is ~10^6 startswith calls of length up to 3000 characters — the string comparisons make it sluggish, and it does redundant work: each prefix rescans products that were already ruled out.
Approach 2 — Sort + binary search (the pattern)
The insight: in a sorted list, all strings sharing a prefix are contiguous, and the block starts exactly at bisect_left(products, prefix) — because the prefix itself sorts immediately before every string that extends it. So the three suggestions are simply the first three entries at or after that insertion point that still start with the prefix.
Binary search is the classical O(log n) technique for locating a value’s position in a sorted sequence by repeatedly halving the search interval; Python’s bisect module implements it.
import bisect
from typing import List
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
result: List[List[str]] = []
prefix = ""
start = 0
for ch in searchWord:
prefix += ch
# Longer prefixes can only move the block rightward, so resume at `start`.
start = bisect.bisect_left(products, prefix, lo=start)
bucket = [p for p in products[start:start + 3] if p.startswith(prefix)]
result.append(bucket)
return result
Walkthrough on products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse". After sorting: ["mobile","moneypot","monitor","mouse","mousepad"].
| prefix | bisect_left → start | next 3 entries | keep (startswith?) |
|---|
"m" | 0 | mobile, moneypot, monitor | all three |
"mo" | 0 | mobile, moneypot, monitor | all three |
"mou" | 3 | mouse, mousepad | both |
"mous" | 3 | mouse, mousepad | both |
"mouse" | 3 | mouse, mousepad | both |
Output matches the expected answer exactly.
- Time: O(n log n · L) for the sort, then O(m (log n + L)) for the m binary searches and constant-size prefix checks.
- Space: O(1) beyond the output.
Approach 3 — Trie
The insight: a trie (prefix tree — a tree keyed by characters where each root-to-node path spells a prefix) answers “all words with this prefix” by walking one node per typed character. Store at each node the up-to-three lexicographically smallest words passing through it, and each query is O(1) after the walk.
from typing import Dict, List
class TrieNode:
def __init__(self) -> None:
self.children: Dict[str, "TrieNode"] = {}
self.best: List[str] = [] # up to 3 smallest words through this node
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
root = TrieNode()
for word in sorted(products):
node = root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
if len(node.best) < 3:
node.best.append(word)
result: List[List[str]] = []
node: TrieNode | None = root
for ch in searchWord:
node = node.children.get(ch) if node else None
result.append(node.best if node else [])
return result
Because products are inserted in sorted order, the first three words appended at any node are automatically the smallest three. On the example, walking m → o → u lands on the node whose best is ["mouse", "mousepad"], and once a character (say a hypothetical "z" next) has no child, node becomes None and every later prefix yields [].
- Time: O(n log n · L) to sort, O(T) to build (T = total characters), O(m) to query.
- Space: O(T) trie nodes.
The trie wins when many queries share one build; for a single searchWord, the bisect version is shorter and just as fast.
Common pitfalls
- Forgetting to sort first — suggestions must be the lexicographically smallest three, not the first three found.
- Taking
products[start:start + 3] without re-checking startswith(prefix) — the three entries after the insertion point may not all match (e.g. prefix "mox" inserts between blocks).
- Assuming matches for a longer prefix can appear before those of a shorter one — they can’t, which is why resuming the search at the previous
start is safe.
- In the trie version, continuing to descend after a missing child instead of emitting
[] for all remaining prefixes.
Pattern takeaway
Sorting turns “everything with property P” into a contiguous block, and binary search finds the block boundary in O(log n). When a query is a prefix, bisect_left on the prefix string itself lands on the first match — a trick worth remembering whenever you need the smallest few strings extending a prefix.