Problem 19.6 · TrieMedium

Search Suggestions System

PatternTrie (Prefix Tree)Binary Search on an Index

What it teaches: Autocomplete: up to three sorted suggestions per typed prefix.

Practise it on judges as “Search Suggestions System”.

The problem

After each character of searchWord is typed, suggest up to three products (lexicographically smallest) that start with the typed prefix. Return the list of suggestion lists.

Example 1

Input: products = [mobile, mouse, moneypot, monitor, mousepad], searchWord = "mouse"
Output: [[mobile, moneypot, monitor], [mobile, moneypot, monitor], [mouse, mousepad], [mouse, mousepad], [mouse, mousepad]]

Constraints

1 ≤ products ≤ 1000
Total characters ≤ 2 × 10⁴

Pattern clues in the wording

→ Autocomplete
→ Top 3 per prefix

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	products = ["mobile","mouse","moneypot","monitor","mousepad"] searchWord = "mouse"	[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
2	products = ["havana"] searchWord = "tatiana"	[[],[],[],[],[],[],[]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Trie with three suggestions per node · O(total characters + n log n)2. Sort + binary search · O(n log n + L log n)

Trie with three suggestions per node

Time O(total characters + n log n) Space O(total characters)

Sort products, then insert each; every node on its path keeps it if it has fewer than three. Walk searchWord, collecting each node's list (empty once the path breaks).

Approach 1

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        List<String> top = new ArrayList<>();
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        Node root = new Node();
        for (String p : products) {
            Node n = root;
            for (char c : p.toCharArray()) {
                if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
                n = n.next[c - 'a'];
                if (n.top.size() < 3) n.top.add(p);
            }
        }
        List<List<String>> out = new ArrayList<>();
        Node n = root;
        for (char c : searchWord.toCharArray()) {
            n = n == null ? null : n.next[c - 'a'];
            out.add(n == null ? new ArrayList<>() : n.top);
        }
        return out;
    }
}

Verdict: Good when many queries share the same products.

Sort + binary search

Time O(n log n + L log n) Space O(1) extra

Sort products. For each prefix, binary search the first product ≥ prefix, then take up to three that start with it.

Approach 2

import java.util.*;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> out = new ArrayList<>();
        String prefix = "";
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            int lo = 0, hi = products.length;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (products[mid].compareTo(prefix) < 0) lo = mid + 1; else hi = mid;
            }
            List<String> row = new ArrayList<>();
            for (int j = lo; j < Math.min(lo + 3, products.length) && products[j].startsWith(prefix); j++) row.add(products[j]);
            out.add(row);
        }
        return out;
    }
}

Verdict: No trie needed for a one-off query.

Before you submit

Edge cases and common mistakes

Test these inputs

No product matches
Fewer than three matches

Mistakes people make

Keeping more than three per node (memory grows with the catalogue).

Interview

Follow-up questions

How would a real search box rank suggestions?