Garden Centre Plant Finder
A garden centre has a touch-screen kiosk where customers look up plants. As a customer types, letter by letter, the screen shows up to three plant names that start with what they have typed so far, in alphabetical order, so they can tap one instead of finishing the word.
The catalogue comes from several suppliers, so the same plant name can be listed more than once. The kiosk should never show the same name twice in one set of suggestions.
Your task
Write suggestPlants(catalogue, typed). For each i from 1 to typed.length, take the first i letters of typed and find the distinct catalogue names that start with them. Return a list with one entry per letter typed: the alphabetically first three of those names, or fewer if fewer exist, or an empty list if none do.
A name that equals the typed letters exactly counts as starting with them.
suggestPlants(catalogue: string[], typed: string) → string[][]
Examples
catalogue = ["mint", "marigold", "maple", "moss", "magnolia", "lavender"] typed = "map"
[["magnolia", "maple", "marigold"], ["magnolia", "maple", "marigold"], ["maple"]]
After "m": five names start with m; the first three alphabetically are magnolia, maple, marigold. After "ma": magnolia, maple, marigold again (mint and moss drop out). After "map": only maple.
catalogue = ["fern", "fig", "fern", "fuchsia"] typed = "fex"
[["fern", "fig", "fuchsia"], ["fern"], []]
fern is listed twice but shown once. After "f": fern, fig, fuchsia. After "fe": fern. After "fex": nothing starts with it, so an empty list.
Constraints
- 1 ≤ catalogue.length ≤ 1,000
- 1 ≤ typed.length ≤ 30, and every name is 1 to 30 letters long
- Only lowercase letters a to z.
Start with brute force
For each prefix of typed, scan the whole catalogue, keep the names that start with it, remove duplicates, sort, and take three.
That is O(L · n log n) for L typed letters and n names, and every keystroke repeats the scan from scratch. On a kiosk with a large catalogue, each keystroke should cost about the same small amount, whatever the catalogue size.
Hints
0 of 4 shown- Hint 1
In the first example, compare the suggestions for "m" and for "ma". Can a name that does not start with "m" ever show up for "ma"? What does each extra letter do to the set of candidates?
- Hint 2
Each extra letter can only narrow the candidates. If the catalogue were sorted alphabetically, where would all the names starting with "ma" sit relative to each other?
- Hint 3
Names sharing a beginning are exactly the names that share a path in a trie. Could each trie node simply remember the answer for its own prefix?
- Hint 4
Sort the catalogue and drop duplicates. Insert the names into a trie in that order; at every node you pass, append the name to the node's list if the list has fewer than 3 entries. Then walk
typedletter by letter and read each node's list. Once a letter has no child, every later answer is an empty list.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every prefix of typed is a node in a trie of the catalogue. If each node already knows its three alphabetically first names, each keystroke is one step down the trie plus a read.
The trick for filling those lists: insert the names in alphabetical order. The first three names to pass through a node are then exactly its three smallest, so each node just keeps the first three it sees.
Trace the first example. Sorted: lavender, magnolia, maple, marigold, mint, moss.
- lavender fills the l-branch. magnolia passes m and ma: both lists get magnolia.
- maple passes m, ma, map: m and ma now hold [magnolia, maple]; map holds [maple].
- marigold passes m and ma: both lists are now full at three names.
- mint and moss pass m, but its list is full, so they are skipped there.
- Typing "map": read m → [magnolia, maple, marigold], ma → the same, map → [maple].
Duplicates are removed before inserting, so a name can never fill two of the three slots. And once a letter has no child, the walk has fallen off the trie and stays off: later letters cannot bring matches back.
A second way works without a trie, using the sorted list from hint 2. Names that start with a prefix sit next to each other in sorted order, so binary search for the first name that is ≥ the prefix and check up to three names from there. That is O(log n · S) per keystroke instead of O(1), but it needs no extra structure.
function suggestPlants(catalogue, typed) {
const names = [...new Set(catalogue)].sort(); // distinct, alphabetical
const root = { kids: new Map(), top: [] };
for (const name of names) {
let node = root;
for (const ch of name) {
if (!node.kids.has(ch)) node.kids.set(ch, { kids: new Map(), top: [] });
node = node.kids.get(ch);
// names arrive in order, so the first 3 to pass are the answer
if (node.top.length < 3) node.top.push(name);
}
}
const result = [];
let node = root;
for (const ch of typed) {
node = node ? node.kids.get(ch) : undefined;
result.push(node ? node.top : []);
}
return result;
}def suggest_plants(catalogue, typed):
names = sorted(set(catalogue)) # distinct, alphabetical
root = {"kids": {}, "top": []}
for name in names:
node = root
for ch in name:
node = node["kids"].setdefault(ch, {"kids": {}, "top": []})
# names arrive in order, so the first 3 to pass are the answer
if len(node["top"]) < 3:
node["top"].append(name)
result = []
node = root
for ch in typed:
node = node["kids"].get(ch) if node else None
result.append(node["top"] if node else [])
return resultRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.