A grocery search box has to paint up to three item names after every letter a shopper types. The first handler filtered the catalog with startsWith, sorted the hits, and kept three. A short list in staging felt instant. The live aisle restarted that scan on every letter, and the dropdown lagged a keystroke behind the keyboard.

After each typed character, return up to three lexicographically smallest products that still share that prefix. A trie already gives the layout. Implement Trie already walks a key, creates missing edges, and reads the end mark. This is an interview writeup, not a layout lecture. Here we only care about ranking the subtree: the typed prefix is exact, and each keystroke needs three lex-smallest words, not a boolean.

The problem

You are given a list of unique lowercase product names and a lowercase searchWord. After each character of searchWord is typed, return a list of lists: up to three lexicographically smallest products that still start with the prefix so far, one inner list per prefix length. If a prefix matches nothing, that row is empty, and every longer prefix is empty too.

products = ["paprika", "parsley", "pasta", "pastry", "peach"], searchWord = "pas"
→  [["paprika", "parsley", "pasta"],
    ["paprika", "parsley", "pasta"],
    ["pasta", "pastry"]]

products = ["kale", "kelp"], searchWord = "kit"
→  [["kale", "kelp"], [], []]

products = ["pesto"], searchWord = "pesto"
→  [["pesto"], ["pesto"], ["pesto"], ["pesto"], ["pesto"]]

Note: This is not a single startsWith boolean, and not one list for the finished word. The outer list has length searchWord.length(). Add and Search Words lets . branch to any child; here every typed letter is exact. The extra job is ranking what sits under that node.

Filter, sort, take three is the honest brute force

After each new character, scan every product, keep those that start with the current prefix, sort them, and take three. Correct. You pay the catalog size n on every keystroke.

List<List<String>> suggestedProductsScan(String[] products, String searchWord) {
    List<List<String>> ans = new ArrayList<>();
    StringBuilder prefix = new StringBuilder();
    for (int i = 0; i < searchWord.length(); i++) {
        prefix.append(searchWord.charAt(i));
        String p = prefix.toString();
        List<String> hits = new ArrayList<>();
        for (String product : products) {
            if (product.startsWith(p)) {
                hits.add(product);
            }
        }
        Collections.sort(hits);
        if (hits.size() > 3) {
            hits.subList(3, hits.size()).clear();
        }
        ans.add(hits);
    }
    return ans;
}

At a short catalog this is a rounding error. On a live aisle you paid a scan of n for a question a character walk already localized: which three lex-smallest words sit under this prefix node?

Walk the prefix; keep three sorted hits on each node

Reuse the Implement Trie node: Node[26] plus endOfWord. Add a List<String> suggestions capped at three, kept in lex order. The trie post’s suggestions() collect is a different shape — a subtree harvest up to a limit, not one three-hit row per typed character — so do not paste it here.

Products may arrive in any order. As you walk a word, offer the full string onto every node along the path, insert it into the sorted list, and drop anything past index 2. Query copies that list after each character; a missing edge dies the walk.

insert("pastry")   p … pastry each hold [pastry]
insert("peach")    p → [pastry, peach]
insert("paprika")  p → [paprika, pastry, peach]
insert("pasta")    pasta belongs before pastry
                   p → [paprika, pasta, pastry]   peach drops
                   pas → [pasta, pastry]
insert("parsley")  parsley belongs between paprika and pasta
                   p  → [paprika, parsley, pasta]
                   pa → [paprika, parsley, pasta]
                   pas unchanged → [pasta, pastry]

searchWord = "pas"
  'p'  copy p    →  paprika, parsley, pasta
  'a'  copy pa   →  paprika, parsley, pasta
  's'  copy pas  →  pasta, pastry

searchWord = "pit"
  'p'  copy p       →  paprika, parsley, pasta
  'i'  missing edge →  []
  't'  still dead   →  []

The Java is that insert plus that walk. offer compares against at most three strings, so a late product that loses to the current third is a no-op. endOfWord is still set the way Implement Trie sets it; query reads the preloaded list, not the mark.

class Solution {
    static final class Node {
        final Node[] children = new Node[26];
        boolean endOfWord;
        final List<String> suggestions = new ArrayList<>(3);
    }

    List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Node root = new Node();
        for (String product : products) {
            insert(root, product);
        }
        List<List<String>> ans = new ArrayList<>();
        Node node = root;
        for (int i = 0; i < searchWord.length(); i++) {
            if (node != null) {
                node = node.children[searchWord.charAt(i) - 'a'];
            }
            if (node == null) {
                ans.add(List.of());
            } else {
                ans.add(new ArrayList<>(node.suggestions));
            }
        }
        return ans;
    }

    void insert(Node root, String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node();
            }
            node = node.children[idx];
            offer(node.suggestions, word);
        }
        node.endOfWord = true;
    }

    void offer(List<String> s, String word) {
        if (s.size() == 3 && word.compareTo(s.get(2)) >= 0) {
            return;
        }
        int i = 0;
        while (i < s.size() && s.get(i).compareTo(word) < 0) {
            i++;
        }
        s.add(i, word);
        if (s.size() > 3) {
            s.remove(3);
        }
    }
}

Time is one pass over every product character to build, and each visit maintains a list of size at most three, then O(m) to walk searchWord and copy at most three references per prefix. Space is the nodes you allocated, plus three string references on each. Do not re-lecture prefix sharing; Implement Trie and the trie post already own the walk and the end mark.

Note: Collecting at query time is legal only if you return the three lexicographically smallest words. Walking children[0..25] and stopping at three end marks is lex because the array is a–z. An insertion-order DFS is not. Prefer the lists on the node so a fat matching subtree is not visited on every keystroke.

What interviewers usually poke next

  • Sort the catalog, then binary-search the prefix. After Arrays.sort(products), each typed prefix is a lower bound plus up to three names that still match. Valid O(n log n) sibling. Mention it; do not turn this board into a second lecture on that pass.
  • Query-time collect instead of lists on the node. Same prefix walk, then a bounded harvest under that node. Must be the three lex-smallest, not an arbitrary DFS. The insert-time lists make that harvest unnecessary.
  • Dead prefix. A missing edge does not shrink the outer list. Every remaining character still contributes [].
  • . wildcards. That branching is Add and Search Words. This prompt’s prefix is exact; the work is ranking.
  • Wider alphabet. Node[26] is a–z. A Map of children is the honest default otherwise — the trie post owns that choice; do not paste a second class here.

You are done with this problem when you can say, out loud, why the filter-and-sort scan is correct, why a boolean startsWith is the wrong shape, and why three sorted strings on each node beat a subtree walk at query time.