On this page
Description
At a party of n people, the celebrity is known by everyone else and knows no one. Asking "does a know b?" for every pair takes n(n - 1) questions. But every single question rules someone out - and n - 1 questions are enough to leave just one possible celebrity.
This skill covers eliminate-then-verify: one pass where each question rules out a candidate, then a check of the single survivor, because the survivor may not be an answer at all. It also covers the counting alternative for when the relationships arrive as a list.
We'll go from simple to more technical:
- The pattern: the celebrity problem, with a running candidate and a verification pass.
- A second flavor: count instead of eliminate (Find the Town Judge).
- Where it shows up (root services, universal sinks, pairwise leader election).
- What breaks it: no verification, half-counted relations, complexity claims, self-relations.
The approach
Java
int findCelebrity(int[][] knows) {
int n = knows.length, candidate = 0;
for (int i = 1; i < n; i++) {
if (knows[candidate][i] == 1) candidate = i; // candidate knows i: candidate isn't it
// otherwise i isn't known by candidate: i isn't it
}
for (int i = 0; i < n; i++) { // verify: elimination alone proves nothing about the survivor
if (i != candidate && (knows[candidate][i] == 1 || knows[i][candidate] == 0)) return -1;
}
return candidate;
}
Python
def find_celebrity(knows: list[list[int]]) -> int:
n, candidate = len(knows), 0
for i in range(1, n):
if knows[candidate][i] == 1:
candidate = i # candidate knows i: candidate isn't it
# otherwise i isn't known by candidate: i isn't it
for i in range(n): # verify: elimination alone proves nothing about the survivor
if i != candidate and (knows[candidate][i] == 1 or knows[i][candidate] == 0):
return -1
return candidate
One question about a and b always eliminates one of them: if a knows b, a knows someone and can't be the celebrity; if not, b isn't known by a and can't be either. A pass over everyone leaves one survivor using n - 1 questions, and a second pass of up to 2(n - 1) questions checks it. Skipping the check is the classic bug: in a party with no celebrity - 0 knows 1, 1 knows 2, and 2 knows no one but isn't known by 0 - the survivor is 2, and only the check reveals the answer is -1. A stack of candidates (pop two, push back the survivor) does the same elimination; the single running candidate is simpler.
A second flavor: count instead of eliminate
When the relationships arrive as a list rather than a question you can ask, counting is simpler. The town judge is trusted by everyone else and trusts nobody: give each person +1 for every trust they receive and -1 for every trust they give. Only the judge can reach n - 1.
Java
int findJudge(int n, int[][] trust) {
int[] score = new int[n + 1];
for (int[] t : trust) {
score[t[0]]--; // trusts someone: can't be the judge
score[t[1]]++;
}
for (int p = 1; p <= n; p++) if (score[p] == n - 1) return p;
return -1;
}
Python
def find_judge(n: int, trust: list[list[int]]) -> int:
score = [0] * (n + 1)
for a, b in trust:
score[a] -= 1 # trusts someone: can't be the judge
score[b] += 1
for p in range(1, n + 1):
if score[p] == n - 1:
return p
return -1
Counting only trusts received isn't enough: a person trusted by everyone who also trusts someone isn't the judge - the -1 for each trust given is what excludes them.
Where you'll see it
Finding a node that everything depends on and that depends on nothing (a root service, a sink in a dependency graph) with pairwise checks, leader election with pairwise comparisons, and "is there a universal sink" queries on adjacency matrices all use eliminate-then-verify.
Which tool for which job?
| You need | Use |
|---|---|
| The one item every comparison rules others out for | a running candidate, then verify |
| Relationships given as a list | received minus given counts |
| A majority element in O(1) space | Boyer-Moore voting, then a counting check |
| The largest value | n - 1 comparisons, each eliminating the smaller |
| The largest and second largest | a knockout tournament, n + log2 n - 2 comparisons |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Returning the survivor unchecked | a party with no celebrity reports one | verify against everyone |
| Counting only how many know someone | someone known by all but knowing one person passes | also check they know no one |
| Calling it O(n) on a matrix | reading the matrix is already O(n^2) | O(n) questions to an oracle |
| Not skipping self-relations | knows[i][i] breaks the checks | skip i == candidate |
| Boyer-Moore without the check | [1, 2, 3] returns 3 as a "majority" | count the candidate afterwards |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. If a knows b, who is eliminated, and why? If a doesn't know b?
Show answer
If a knows b, a is out - a celebrity knows no one. If a doesn't know b, b is out - a celebrity is known by everyone, including a.
2. Why is the verification pass necessary?
Show answer
Elimination proves everyone else is not the celebrity, but the survivor might not be one either - there may be no celebrity. Checking the survivor against everyone (it knows nobody, everybody knows it) decides.
3. For the town judge, why subtract 1 for each trust given?
Show answer
The judge must trust nobody. A person trusted by all n - 1 others who also trusts someone would reach n - 1 by counting received trusts alone; the -1 per trust given pushes them below n - 1.
Key takeaways
- One question eliminates one candidate: n - 1 questions leave one survivor.
- Always verify the survivor; there may be no answer.
- The cost is O(n) questions, not O(n) to read an n x n matrix.
- With relations given as a list, count received minus given (town judge).