Autocomplete as an Algorithms Problem

A search-as-you-type input is one of the most common frontend features and one of the most commonly built badly. A naive implementation ships in a weekend and fails quietly the moment the list is big, the user is on a slower phone, or the network is flaky.

This lesson treats the feature as what it actually is: four separate algorithm problems bolted together.

• Prefix matching — find the candidates that start with the current query.
• Ranking — choose and order the best N of those candidates.
• Debouncing — don't do the work on every keystroke.
• Cancellation — don't let a slow earlier request overwrite a fast later one.

Each of those has been covered on its own elsewhere in the track. Putting them together is where the design decisions live.

Prefix matching: three implementations

Three plausible ways to find the candidates that start with the query. Each has a complexity profile and a sensible-use-case.

1. Linear filter

function suggest(query, titles) {
  return titles
    .filter((t) => t.toLowerCase().startsWith(query.toLowerCase()))
    .slice(0, 10);
}

Complexity: O(n) per keystroke, where n is the number of titles. Perfectly fine up to a few thousand items; feels laggy at tens of thousands on a mid-range phone.

When it's the right answer: small lists (a dropdown of countries, a tag picker, a project list under a few thousand items). Don't over-engineer.

2. Sorted index + binary search

// Once, at startup:
const sorted = [...titles].sort();
 
// Per keystroke:
function suggest(query) {
  const lower = lowerBound(sorted, query);
  const upper = lowerBound(sorted, nextAfter(query)); // query + highest char
  return sorted.slice(lower, Math.min(upper, lower + 10));
}

Complexity: O(log n) to find the range of titles starting with the query, then O(k) to slice k suggestions. Preprocessing is one O(n log n) sort at startup.

When it's the right answer: a static or rarely-updated list of tens of thousands to low-millions of items. Small code, fast per-lookup, no exotic data structure to maintain.

3. Trie

class TrieNode {
  constructor() {
    this.children = new Map();
    this.titles = []; // sorted/ranked, truncated to top-k during build
  }
}
 
function buildTrie(titles) {
  const root = new TrieNode();
  for (const title of titles) {
    let node = root;
    for (const ch of title.toLowerCase()) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
      if (node.titles.length < 10) node.titles.push(title);
    }
  }
  return root;
}
 
function suggest(query, root) {
  let node = root;
  for (const ch of query.toLowerCase()) {
    node = node.children.get(ch);
    if (!node) return [];
  }
  return node.titles;
}

Complexity: O(length of query) per lookup — independent of n. Memory is higher: the trie stores a node per character of each unique prefix, and the per-node suggestion list adds more.

When it's the right answer: very large datasets, high query frequency, and lookups whose latency has to stay flat as the dataset grows. Autocomplete widgets with built-in ranked suggestions (like a search box that shows "top matches") are a natural fit, because you can precompute the top-k at every node during build.

Ranking: the piece that separates working from good

A list of raw prefix matches isn't a useful autocomplete unless it's ordered. Three common rankings, in order of complexity:

• Alphabetical. The default if you did nothing. Works for countries, usernames by letter, anything where the user is scanning down a list for a thing they know.
• Popularity / frequency. Each candidate has a score (usage count, click-through rate, search-log frequency). The top-k sorted by score goes first. Needs a score column and a way to keep the ranking up to date.
• Personalisation. Score depends on this user's history, or the current page context ("recent projects first," "friends first"). More signal to compute, higher payoff.

The relevant algorithmic choice is: once you've found the set of prefix matches, how do you find the top-k ranked?

• If k is small (10 or 20) and the set of matches is large, use a min-heap of size k — push each match, pop if size exceeds k. O(m log k) for m matches.
• If you've pre-computed ranked suggestions at each trie node during build (every node stores "my top 10 completions, by score"), lookup is O(k) — the ranking work has been amortised into the build.

The server-side autocomplete at scale (Google, GitHub) runs ranked indices of exactly this shape — the trie isn't just a lookup, it's a pre-ranked lookup.

Debounce and cancel: the UX plumbing

Prefix-matching the local dataset is cheap. Fetching suggestions from a server on every keystroke is not. The two patterns that make this bearable were both covered elsewhere in the course; here's how they compose for autocomplete.

let active = null;
 
const onInput = debounce(async (query) => {
  if (!query) return render([]);
 
  active?.abort();
  active = new AbortController();
 
  try {
    const res = await fetch(`/autocomplete?q=${encodeURIComponent(query)}`, {
      signal: AbortSignal.any([active.signal, AbortSignal.timeout(2000)]),
    });
    render(await res.json());
  } catch (err) {
    if (err.name === "AbortError" || err.name === "TimeoutError") return;
    throw err;
  }
}, 150);

Three lines are doing the work:

• debounce(..., 150) — fire at most every 150ms of continuous typing. Delays the request until typing settles.
• active?.abort() — cancel the previous in-flight request. Even within a debounce interval, if the user types fast enough that requests overlap, the older one is discarded.
• AbortSignal.any([active.signal, AbortSignal.timeout(2000)]) — belt and braces: user-triggered cancellation OR a 2-second server timeout, whichever fires first.

Only the latest response can reach render(). The stale-result race described earlier in the course is prevented by the cancellation, not by the debounce — if the user types just slow enough that each keystroke clears the debounce timer, you still fire a request per keystroke and still need the cancel to avoid the race.

Client-side vs server-side: an honest choice

A tempting design: ship the entire dataset to the browser at startup, build a trie, do lookups locally. "Instant and offline!"

It works well in one specific case: the dataset is small enough that shipping it doesn't hurt first-paint, and it changes rarely enough that the shipped copy is correct. Think: the list of countries, the list of users in a small team, a short enum.

It fails for large datasets:

• First-byte cost. Shipping 100k titles is bandwidth, battery, and parse time the user paid for before they typed anything.
• Memory. The trie for 100k titles can be tens of MB. On a mid-range phone, that's not free.
• Staleness. The dataset changes between page load and the user's search. The shipped copy is wrong whenever a title was added or removed since.
• Ranking signal. The server knows "which of these are the most-clicked for this query right now." A client-side copy doesn't — unless you also ship the ranking data, which usually means shipping even more.

The honest sentence: client-side autocomplete is for small, stable datasets; server-side autocomplete with debounce + cancel is for everything else. For small lists, prefer linear filter; it's simpler and the implementation complexity isn't worth paying for a dataset where O(n) is already fast.

Putting it all together: a decision tree

A rough decision tree worth remembering:

Every production autocomplete lives at one of those three levels. Picking the right one is a cheaper decision than picking any of them and then over- or under-building for the actual scale.

What to remember

• Autocomplete is four problems: prefix matching, ranking, debouncing, cancellation. Each has already been covered in this track; the design is how they compose.
• Three prefix-match implementations, from cheapest to most scalable: linear filter (small lists), sorted-array + binary search (static medium lists), trie (large lists / high-frequency lookup / pre-ranked suggestions).
• Ranking is what separates a working autocomplete from a good one. Alphabetical is the free default; popularity and personalisation need a score and a way to keep it fresh. Pre-ranking at each trie node makes top-k lookup O(k).
• Debouncing alone doesn't fix the stale-result race. Pair it with per-request cancellation (AbortController) and an overall timeout (AbortSignal.timeout + AbortSignal.any).
• Client-side autocomplete is for small, stable datasets. Large datasets belong on a server-side endpoint with debounce + cancel + ranked response.
• Decision tree: small → filter; medium static → sorted + binary search; large or ranked → server-side.