TL;DR
Sort once, then binary search each prefix with bisect_left. Time is O(n·L·log n) for the sort plus O(m·L·log n) for the searches; O(1) extra space beyond the output. Here n is the number of products, m the length of searchWord, and L the maximum product length.
Approach 1 — Brute force
Sort the products so they are in lexicographic order. Then for each prefix of searchWord, scan the whole list and keep the first three products that start with the prefix.
from typing import List
def suggestedProducts(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 on strings up to 3000 characters long. The repeated full-length comparisons are slow, and the work is redundant: each prefix rescans products 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
def suggestedProducts(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·L·log n) for the sort, then O(m·L·log n) for the m binary searches, since each search does O(log n) string comparisons of up to L characters.
- 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.
For the example, the branch under mo looks like this, with each node’s stored best list shown:
flowchart TD
R((root)) --> M["m"]
M --> O["o"]
O --> B["b — best: mobile"]
O --> N["n — best: moneypot, monitor"]
O --> U["u — best: mouse, mousepad"]
Typing m → o → u walks to the u node, whose best is ["mouse", "mousepad"].
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
def suggestedProducts(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 is preferable 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.