Search Suggestions System

hard

Return up to 3 lexicographically sorted suggestions while typing each prefix

Search Suggestions System

Key Insight

Store products in trie and keep best suggestions at each node to avoid rescanning the full word list.

Step 1Insert Sorted Products
Array
mobile
0
mouse
1
moneypot
2
monitor
3
HashMap
m:4
mo:4
mon:2

mobile, mouse, moneypot, monitor are inserted and each node keeps top 3 candidates.

1 / 3

Learn the Pattern

Hash MapUse a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.
Practice the Code

Step-by-Step Walkthrough: Search Suggestions System

Store products in trie and keep best suggestions at each node to avoid rescanning the full word list.

  1. Insert Sorted Products

    mobile, mouse, moneypot, monitor are inserted and each node keeps top 3 candidates.

  2. Type "mo"

    Traverse to node "mo" and read precomputed suggestion list.

  3. Continue Typing

    Longer prefix narrows to fewer matches but still reads direct top-3 cache.