Candidate elimination (Guess the Word)

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A friend picks a secret six-letter word from a list of candidates you can both see. You guess a word from the list, and the friend answers only with a number: how many positions match exactly. You have ten guesses. With six candidates you might try them one by one and get lucky, but with a hundred candidates and ten guesses, guessing in order fails most of the time.

The by-hand insight is that each answer tells you something about every candidate, not just the one you guessed. If your guess scores 2, the secret must have exactly 2 positions in common with your guess. Any candidate that has 0, 1, 3 or more positions in common with your guess cannot be the secret, and can be crossed off.

Build the structure, one piece at a time

Piece one: a candidate set, starting as the whole list. Define match(a, b) as the number of positions where words a and b have the same letter.

Piece two: the filter. After guessing g and hearing the answer k, keep only the candidates c with match(g, c) = k. On the six-word example, guessing abcczz and hearing 2 leaves 2 candidates; guessing ccbazz among those and hearing 2 leaves 1; guessing that one scores 6 and the game is over in three guesses.

Piece three: choosing the guess well. Not every guess is equally informative. For a candidate g, imagine every possible answer 0 … 6 and count how many candidates would survive each answer. The worst case for g is the largest of those counts. Pick the g whose worst case is smallest; it is the guess that splits the candidates most evenly, so whatever the answer, the fewest survive:

This is the same shape as binary search: a question whose answer discards as much as possible. In binary search each answer discards half; here the alphabet of answers is 0 to 6, so a good guess can discard much more than half.

Why it is correct

The invariant is that the secret is always in the candidate set. It starts true because the secret is on the list. After a guess g with answer k, the secret s satisfies match(g, s) = k by the rules of the game, so it is kept by the filter. Only words that could not be the secret are discarded. The process ends when a guess scores the full length, which happens at the latest when the set shrinks to one word and we guess it.

Choosing the minimax guess does not affect correctness, only how fast the set shrinks. Any guess from the set keeps the invariant.

Why it is fast

Choosing a guess compares every candidate with every other, n² pairs, each comparison L letters, so O(n² L) per round; the filter is O(n L). What matters more is how many rounds are needed. A guess that scores 0 against most words, which is common when words share few letters, still leaves most of them; the minimax choice avoids that. In practice the candidate set shrinks by a large factor per round, and the problem's ten guesses are enough for a hundred words. There is a counting bound too: if every answer left at most a fraction 1/r of the set, n words would need about log_r n rounds.

rounds ≈ log_r n, where each answer keeps at most 1/r of the candidates

How to recognise it in an interview

Cues: an "interactive" problem, an oracle or judge that answers a limited query, a cap on the number of queries, "guess", "master", "the array is sorted but you can only call get(i)". Say: "every answer rules out candidates, so I will keep the set of candidates consistent with all answers and choose each query to shrink that set as much as possible in the worst case".

Guess the Word is the walk-through above. Guess Number Higher or Lower is the same idea where the answer is higher, lower or equal, which makes the best query the midpoint, so it is binary search. Find in Mountain Array queries an oracle with a limited budget and uses three binary searches: one for the peak, then one on each slope.

02The idea in one line

Guess the word that would split candidates most evenly; keep only consistent ones.

Reach for it when: Guess the word, find in mountain array, search unknown-size array, master-mind style.

Cost: O(n²·L) per round.

03The walk-through, step by step

The video works one example: Guess the Word with 6 candidates. These are its captions in order, so you can follow without the video or check a step you missed.

1. Every surviving candidate must agree with all past answers
2. Score each candidate by how evenly it splits the others by match count
3. Guess abcczz: smallest worst-case bucket (2)
4. The judge answers 2 matching positions
5. Keep only words with exactly 2 matches vs abcczz: 2 left
6. Guess ccbazz: smallest worst-case bucket (1)
7. The judge answers 2 matching positions
8. Keep only words with exactly 2 matches vs ccbazz: 1 left
9. Guess eiowzz: smallest worst-case bucket (1)
10. The judge answers 6 matching positions
11. 6 of 6: found the secret in 3 guesses
12. Each guess costs O(n²·L) to choose; candidates shrink fast

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Interactive: none in this topic.