Imagine you walk into a party with a few hundred guests. You don't know who anyone is, but you're told that one person there might be a celebrity. You can only ask questions of the form:
"Hey, do you know that person over there?"
How many questions do you need to ask to find the celebrity, or to prove there isn't one?
My first instinct when I met this problem was "just ask everyone about everyone." It works, but it's slow. By the end of this post you'll see how to do it with one pass and no extra memory.
Grab a coffee. We'll build this up step by step.
What exactly is a celebrity?
In this problem, a celebrity is someone who satisfies both of these rules:
- Everyone knows them.
- They know nobody.
That's it. Two rules, and both must hold.
You're given a square matrix M of size n x n:
-
M[i][j] = 1means personiknows personj -
M[i][j] = 0means personidoes not know personj
Your job: return the celebrity's index, or -1 if there isn't one.
A tiny example
M = [
[0, 0, 1, 0], # person 0 knows only person 2
[0, 0, 1, 0], # person 1 knows only person 2
[0, 0, 0, 0], # person 2 knows nobody
[0, 1, 1, 0], # person 3 knows persons 1 and 2
]
Here is the same thing as a picture. An arrow A -> B means "A knows B":
0 -----+
|
v
1 ---> 2 <--- 3
^ |
| |
+-------+
(3 also knows 1)
Everyone points at person 2, and person 2 points at nobody. So the answer is 2.
💡 Quick sanity check: can there ever be two celebrities? Think about it for a second before reading on.
Answer
No. If A and B were both celebrities, then A would have to know B (because everyone knows a celebrity). But a celebrity knows nobody. That's a contradiction, so there is at most one celebrity. This fact is the secret ingredient of the fast solution later.
Attempt 1: Brute force
The most natural idea is to test every person one by one.
For each person c:
- Check that
cknows nobody (their entire row is 0, apart from themselves). - Check that everyone knows
c(their entire column is 1, apart from themselves).
def find_celebrity_brute(M):
n = len(M)
for c in range(n):
is_celebrity = True
for i in range(n):
if i == c:
continue
# c must not know i, and i must know c
if M[c][i] == 1 or M[i][c] == 0:
is_celebrity = False
break
if is_celebrity:
return c
return -1
How slow is it?
We have an outer loop over n people and an inner loop over n people.
Time: O(n²), Space: O(1)
For 1,000 people that's about a million checks. For 100,000 people it's ten billion. That's the point where your laptop fan starts to sound like a jet engine.
Can we do better? Let's look for wasted work.
The key insight: every question kills someone
Here's the idea that changes everything. Pick any two people, A and B, and ask just one question: "Does A know B?"
There are only two possible answers, and both of them eliminate somebody.
| Answer | What it tells us | Who is eliminated? |
|---|---|---|
| Yes, A knows B | A knows someone, but a celebrity knows nobody | A can't be the celebrity |
| No, A doesn't know B | B isn't known by everyone, but a celebrity must be | B can't be the celebrity |
Read that table once more. It's the entire trick.
One question, one person eliminated. Always. No matter what.
So if we start with n people, after n - 1 questions we're left with exactly one candidate. Not the celebrity yet, just the only person who hasn't been ruled out.
Attempt 2: Eliminate with a stack
Let's turn that insight into an algorithm. A stack is a nice way to picture it:
- Push everyone onto the stack.
- Pop two people,
aandb. - If
aknowsb, thenais out, so pushbback. Otherwisebis out, so pushaback. - Repeat until one person is left.
- Verify that person (more on this soon).
def find_celebrity_stack(M):
n = len(M)
stack = list(range(n))
while len(stack) > 1:
a = stack.pop()
b = stack.pop()
if M[a][b] == 1: # a knows b, so a is not a celebrity
stack.append(b)
else: # a doesn't know b, so b is not a celebrity
stack.append(a)
candidate = stack.pop()
# Verification step
for i in range(n):
if i == candidate:
continue
if M[candidate][i] == 1 or M[i][candidate] == 0:
return -1
return candidate
Time: O(n), Space: O(n) for the stack.
We got linear time. But storing everyone in a stack feels like overkill. Can we get rid of it?
Attempt 3: Two pointers, no extra memory
Why keep a stack when we only ever hold one survivor at a time? We can just remember a single variable called candidate.
The idea:
- Start by assuming person
0is the celebrity. - Walk through everyone else, one at a time.
- If the current candidate knows person
i, the candidate is out andibecomes the new candidate. - Otherwise
iis out, and we keep our candidate.
def find_celebrity(M):
n = len(M)
# Phase 1: find a possible candidate
candidate = 0
for i in range(1, n):
if M[candidate][i] == 1:
candidate = i
# Phase 2: verify the candidate
for i in range(n):
if i == candidate:
continue
if M[candidate][i] == 1 or M[i][candidate] == 0:
return -1
return candidate
That's the whole solution. Two small loops.
Time: O(n), Space: O(1)
Let's trace it by hand
Using our earlier matrix:
M = [
[0, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 1, 1, 0],
]
Phase 1: find the candidate
| Step | candidate | i | M[candidate][i] |
Decision |
|---|---|---|---|---|
| start | 0 | - | - | Assume 0 |
| 1 | 0 | 1 | 0 | 0 doesn't know 1, so 1 is out. Keep 0 |
| 2 | 0 | 2 | 1 | 0 knows 2, so 0 is out. Candidate becomes 2 |
| 3 | 2 | 3 | 0 | 2 doesn't know 3, so 3 is out. Keep 2 |
Candidate after phase 1: 2.
Phase 2: verify
| Person | Does 2 know them? (must be 0) | Do they know 2? (must be 1) | OK? |
|---|---|---|---|
| 0 | M[2][0] = 0 |
M[0][2] = 1 |
✅ |
| 1 | M[2][1] = 0 |
M[1][2] = 1 |
✅ |
| 3 | M[2][3] = 0 |
M[3][2] = 1 |
✅ |
All checks pass, so the celebrity is person 2. 🎉
Wait, why do we need Phase 2?
This is the part most beginners (including me, the first time) skip.
Phase 1 only tells us: "everyone else has been ruled out." It does not tell us the survivor is actually a celebrity. Maybe there is no celebrity at all!
Try this matrix where nobody knows anybody:
M = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
]
Phase 1 hands us person 0 as the candidate (nobody ever knew anyone, so the candidate never changed). But person 0 is not a celebrity, because nobody knows them. Phase 2 catches this and correctly returns -1.
Rule of thumb: elimination finds the only possible answer. Verification confirms it's a real answer.
Comparing all approaches
| Approach | Time | Space | Idea |
|---|---|---|---|
| Brute force | O(n²) | O(1) | Test every person fully |
| Stack elimination | O(n) | O(n) | Eliminate one person per question |
| Two pointer candidate | O(n) | O(1) | Same idea, no stack needed |
And here's how the number of questions grows as n grows:
| n (people) | Brute force (about n²) | Optimized (about 3n) |
|---|---|---|
| 10 | 100 | 30 |
| 1,000 | 1,000,000 | 3,000 |
| 100,000 | 10,000,000,000 | 300,000 |
The optimized version needs about n - 1 questions to find a candidate, plus about 2(n - 1) to verify. That is roughly 3n, which is still O(n).
Common mistakes to avoid
- Forgetting the verification phase. The most common bug. See the all zeros matrix above.
-
Checking
M[i][i]. A person knowing themselves is usually0or ignored. Always skipi == candidate. -
Mixing up the direction.
M[a][b]means "a knows b", not the other way around. Read it out loud while coding. -
Using the wrong elimination rule. If
aknowsb, eliminatea(notb). I've flipped this more than once at 1 AM.
The interview version
In interviews you often don't get the matrix. You get a function instead:
def knows(a, b) -> bool: ...
The goal is the same, and the number of calls to knows is what gets measured. The same algorithm drops right in:
def findCelebrity(n):
candidate = 0
for i in range(1, n):
if knows(candidate, i):
candidate = i
for i in range(n):
if i == candidate:
continue
if knows(candidate, i) or not knows(i, candidate):
return -1
return candidate
A small optimization worth mentioning to your interviewer: you can cache results of knows so you never ask the same question twice.
Quick quiz
Test yourself before looking at the answers.
Q1. In Phase 1, candidate = 4 and M[4][7] = 0. What happens?
Answer
Person 4 doesn't know person 7, so 7 cannot be the celebrity (a celebrity must be known by everyone). We keep 4 as the candidate and move on.
Q2. Can the algorithm return a wrong answer without Phase 2?
Answer
Yes. Phase 1 always produces a candidate, even when no celebrity exists. Phase 2 is what confirms it.
Q3. What would the time complexity be if we verified every person instead of only the final candidate?
Answer
That's just the brute force approach again, so O(n²). The whole point of elimination is that we only fully verify one person.
Key takeaways
- A celebrity is known by everyone and knows no one.
- There can be at most one celebrity.
- Every question
knows(a, b)rules out exactly one of the two people. - Eliminate first, verify second.
- Brute force is O(n²). The elimination approach is O(n) time and O(1) space.
The bigger lesson isn't about celebrities. It's this question:
"Can each step of my algorithm throw away part of the problem?"
That mindset shows up in binary search, two pointers, monotonic stacks, and many other patterns. Once you start looking for it, you'll see it everywhere.
🥋 Want to practice problems like this?
Understanding the solution is one thing.
Being able to solve a new problem on your own is another.
That's why I've been exploring ScaleDojo, a hands-on platform for practicing system design, LLD, API design, and algorithmic problem-solving.
Instead of only reading the solution, you can practice concepts through interactive challenges and get feedback on your approach.
If you're preparing for technical interviews or simply trying to become better at problem-solving, it's worth checking out:
More practice problems
If you want to keep going with the same pattern, try these next:
- Find the Celebrity (LeetCode 277)
- Find the Town Judge (LeetCode 997), a very close cousin
- Find Center of Star Graph (LeetCode 1791)
Your turn
Did you solve this with the stack, two pointers, or something even cleverer? Drop your approach (or your favorite language) in the comments. I'd love to see a Rust or Go version!
And one more question for you: what's the first thing you'd check if your app slowed down after hitting 10x traffic? I'm curious what everyone's instinct is.
If this post helped you, a ❤️ or 🦄 helps more beginners find it, and following me means you won't miss the next one in this series. Thanks for reading, and happy coding!
Top comments (1)
Great work!