DEV Community

Ritesh Gupta
Ritesh Gupta

Posted on

The Celebrity Problem: From Brute Force to O(n)

#algorithms #beginners #computerscience #python

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:

  1. Everyone knows them.
  2. 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] = 1 means person i knows person j
  • M[i][j] = 0 means person i does not know person j

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
]
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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 c knows 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
Enter fullscreen mode Exit fullscreen mode

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:

  1. Push everyone onto the stack.
  2. Pop two people, a and b.
  3. If a knows b, then a is out, so push b back. Otherwise b is out, so push a back.
  4. Repeat until one person is left.
  5. 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
Enter fullscreen mode Exit fullscreen mode

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 0 is the celebrity.
  • Walk through everyone else, one at a time.
  • If the current candidate knows person i, the candidate is out and i becomes the new candidate.
  • Otherwise i is 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
Enter fullscreen mode Exit fullscreen mode

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],
]
Enter fullscreen mode Exit fullscreen mode

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],
]
Enter fullscreen mode Exit fullscreen mode

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

  1. Forgetting the verification phase. The most common bug. See the all zeros matrix above.
  2. Checking M[i][i]. A person knowing themselves is usually 0 or ignored. Always skip i == candidate.
  3. Mixing up the direction. M[a][b] means "a knows b", not the other way around. Read it out loud while coding.
  4. Using the wrong elimination rule. If a knows b, eliminate a (not b). 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: ...
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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:

👉 Try ScaleDojo

More practice problems

If you want to keep going with the same pattern, try these next:

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 (0)