Find the Celebrity
Among n people, a celebrity is known by everyone and knows no one. Find them with O(n) knows(a,b) queries, or return −1.
- 2 <= n <= 100
- knows(a, b) answers in O(1)
- At most one celebrity exists; return -1 if there is none
Intuition
Find the celebrity defines one among n people who is known by everyone else and knows nobody. You can only ask knows(a, b), and the target is O(n) queries — far fewer than the n² needed to fill in the whole matrix.
The key observation is that a single query always eliminates someone, whatever the answer:
- If knows(a, b) is true, a is not the celebrity — a celebrity knows nobody.
- If it is false, b is not the celebrity — everyone knows a celebrity.
There is no wasted question. So sweep once with a running candidate: start with person 0, and for each next person ask whether the candidate knows them. If yes, the candidate is eliminated and that person becomes the new candidate. If no, the other person is eliminated and the candidate stands. After n−1 queries, exactly one person has never been eliminated.
That survivor is the only possible celebrity, but not yet a confirmed one. The elimination proves everyone else fails; it does not prove this person succeeds — the array may contain no celebrity at all. So a verification pass is mandatory: check that the candidate knows nobody and that everybody knows them, which costs 2n more queries.
Total: about 3n queries, comfortably O(n).
When every pair could be queried but the answer is unique, look for a question whose answer eliminates one candidate whichever way it goes. knows(a, b) does exactly that: if true, a can't be the celebrity; if false, b can't. One pass of n−1 such questions leaves a single survivor, which you then verify. That eliminate-one-per-question idea is the whole technique.
Approach
Before reading on: price up what enumerating every case costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(1) space.
See that every query removes a candidate
knows(a, b) being true rules out a; being false rules out b. No query is ever wasted, which is what makes a single linear sweep enough to narrow n people down to one.
Sweep to a single survivor
Start with candidate 0 and loop i from 1 to n−1. If the candidate knows i, set the candidate to i; otherwise keep it. After n−1 queries one person remains — the only one never eliminated.
Do not skip the verification
The sweep proves nobody else can be the celebrity; it does not prove the survivor is one. A group with no celebrity still produces a survivor, so returning it unchecked is wrong.
Verify in both directions
For every other person i, confirm that the candidate does not know i and that i knows the candidate. Any failure means no celebrity exists — return −1. This costs 2(n−1) queries.
Cost in queries
About n−1 for the sweep plus 2(n−1) to verify, giving O(n) queries and O(1) space. Compare with the naive approach of building the full knows-matrix at O(n²) — the saving comes entirely from the observation that one question eliminates one person.
Solution & live demo
Common pitfalls
Skipping the verification pass
for i in range(1, n):
if knows(cand, i): cand = i
return candfor i in range(n):
if i != cand and (knows(cand, i) or not knows(i, cand)):
return -1
return candThe first pass only proves that everyone else is disqualified — it never proves the survivor qualifies. When no celebrity exists, some candidate still survives, and returning it is wrong. The second pass is what distinguishes "last one standing" from "actually a celebrity".
Comparing the candidate against itself during verification
for i in range(n):
if knows(cand, i) or not knows(i, cand):
return -1for i in range(n):
if i != cand and (knows(cand, i) or not knows(i, cand)):
return -1knows(cand, cand) is undefined by the problem and typically returns False, so not knows(i, cand) fires and a genuine celebrity is rejected. The candidate must be excluded from its own check.
Checking every pair
for a in range(n):
for b in range(n):
...cand = 0
for i in range(1, n):
if knows(cand, i): cand = iThat's O(n²) calls when O(n) suffices to find the candidate. Each query already rules someone out permanently, so re-asking about eliminated people is wasted work.
Edge cases
Verification fails → −1. The elimination pass alone can't detect this.
Sole person is trivially the celebrity — verification passes vacuously.