Counting and Voting
What is this?
These tricky problems hinge on one observation: you rarely need to count something directly. Instead, you let opposing elements cancel each other out, eliminate candidates one comparison at a time, or keep a few running tallies and watch the answer emerge from whatever survives. The clever move is realizing that a handful of counters can replace a full bookkeeping pass.
💡 Fun fact: The Boyer-Moore majority vote works because anything occupying more than half the array outlasts every possible cancellation — pair off every other element against it and the majority still has votes left standing.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: When something dominates a collection, you don't have to count it directly — you can let opposing elements cancel out, eliminate candidates pairwise, or track a few running counts and watch the answer emerge from what survives.
The pattern
The cleanest version is voting: keep one candidate and a count. A matching element raises the count, a differing one lowers it, and when it hits zero you adopt the next element. Anything that occupies more than half the array is guaranteed to outlast every cancellation and end as the survivor.
The same cancellation logic powers elimination: ask one comparison per step that lets you discard a candidate permanently, so a linear sweep narrows many possibilities down to one (then verify it).
A softer cousin is the running tally: instead of finding a survivor, you maintain counts of in-progress states and read the answer off the maximum or final tally — no per-element bookkeeping beyond a handful of counters. The shared theme is counts that move against each other so the structure of the answer falls out of the arithmetic.
The problems
- Majority Element — Boyer-Moore voting: hold a candidate and a count, cancel on mismatch; the element appearing more than
n/2times is what remains. - Find the Celebrity — one elimination pass: each "does A know B" either rules out A or rules out B, leaving a single candidate to confirm.
- Minimum Moves to Equal Array Elements — reframe "raise all but one" as "lower one," so the answer is the sum of differences from the minimum.
- Minimum Number of Frogs Croaking — keep running counts of frogs at each c-r-o-a-k stage; the peak number simultaneously mid-croak is the minimum frogs needed.
Key takeaways
- Cancellation reveals dominance — a majority survives every pairing.
- One smart comparison eliminates — discard a candidate per step, then verify.
- Reframe the operation — "increment all but one" equals "decrement one."
- Running counts beat full counts — track stages, read the peak.
Find the Celebrity
Core idea: A single
knows(a, b)call always eliminates one of the two people as a possible celebrity — so one linear sweep is enough to crushnsuspects down to a single surviving candidate. Then you spend a second pass to verify that candidate really is the celebrity (or prove no one is). Two passes, O(n) calls, no extra data structure.
Problem, rephrased
You're at a party with n people, labelled 0 … n-1. Somewhere in the room there might be a celebrity:
- Everyone at the party knows the celebrity.
- The celebrity knows no one — too famous to bother.
You can't see faces. Your only tool is a one-way question:
knows(a, b) -> True if person a knows person b
False otherwise
Each call is a real interaction (think: an expensive directory lookup or a network probe), so you want to make as few as possible. Return the celebrity's label, or -1 if the party has no celebrity.
Two structural facts make this tractable:
- There is at most one celebrity. (Two celebrities can't coexist — see the Q&A.)
- The celebrity is the unique person with out-degree 0 (knows nobody) and in-degree n-1 (everybody knows them).
Inputs / outputs
Think of the relationships as a matrix M where M[a][b] == 1 means "a knows b". Row = who I know, column = who knows me.
n |
knows matrix (rows = a, cols = b) |
celebrity | answer |
|---|---|---|---|
| 2 | [[1,1],[0,1]] |
person 1 | 1 |
| 3 | [[1,1,0],[0,1,0],[1,1,1]] |
person 1 | 1 |
| 3 | [[1,1,0],[0,1,1],[0,0,1]] |
none | -1 |
| 1 | [[1]] |
person 0 | 0 |
(The diagonal M[i][i] is 1 by convention — you "know" yourself — and never actually queried.) In the second row, person 1 knows nobody else and is known by everyone, so person 1 is the celebrity. In the third row, no one fits, so the answer is -1.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson