Algorithm

The Celebrity Problem

Stacks & Queues Pattern

The Celebrity Problem

Suppose you are at a party with n people labeled 0 to n-1. Among them, there may exist one celebrity: everyone knows the celebrity, but the celebrity knows no one. Given a helper function knows(a, b) that returns true if person a knows person b, find the celebrity or return -1 if none exists. Minimize the number of API calls.

CONSTRAINTS
  • 2 <= n <= 1000
  • knows(a, b) counts as one API call
  • There is at most one celebrity
EXAMPLE 1
Input: n=3, knows: 0 knows 1, 2 knows 1
Output: 1
Person 1 is known by 0 and 2. Person 1 knows no one. Celebrity confirmed.
EXAMPLE 2
Input: n=2, nobody knows each other
Output: -1
No one is universally known. No celebrity exists.
EXAMPLE 3
Input: n=3, everyone knows everyone
Output: -1
All know each other. A celebrity cannot know anyone, so no celebrity.
Can there be more than one celebrity?
No. If A is a celebrity, every other person including B must know A. But A cannot know anyone—including B. So B cannot also be a celebrity, because A doesn't know B (failing the 'everyone must know B' rule).
Is the verification pass mandatory after elimination?
Yes. Elimination narrows to one suspect but does not prove they are the celebrity. The verification pass confirms: all others know them, and they know no one.

Suppose you are looking for a celebrity in a crowd of N people. In a brute-force world, you would have to ask everyone about everyone else, which takes N squared questions. But identifying a celebrity has two strict rules that we can use for rapid elimination:
1. A celebrity knows no one.
2. Everyone knows the celebrity.

The magic insight is that the single question "Does Person A know Person B?" always guarantees the death of exactly one suspect. If the answer is Yes, then A cannot be the celebrity (Rule 1). If the answer is No, then B cannot be the celebrity (Rule 2).

The Elimination Round

Instead of scanning pairwise, we use a Stack to narrow down the suspects.
1. The Setup: Put everyone into the "Suspect Stack."
2. The Face-Off: Pop the top two suspects, A and B. Ask: "Does A know B?"
- If Yes: A is disqualified. Push B back into the stack.
- If No: B is disqualified. Push A back into the stack.
3. The Survivor: Every time we ask a question, one person is removed forever. After N-1 questions, only one person remains in the stack.
4. The Verification: The survivor is our prime suspect, but we haven't proven they are a celebrity yet. We must do a final check: Do they truly know zero people, and does every single other person know them?

Code Blueprint
text
stack = [0, 1, ..., n-1]

// Phase 1: Narrow down to 1 candidate
WHILE stack.SIZE > 1:
    A = stack.POP()
    B = stack.POP()
    
    IF knows(A, B): 
        stack.PUSH(B) // A is not a celebrity
    ELSE:
        stack.PUSH(A) // B is not a celebrity

candidate = stack.POP()

// Phase 2: Verify the survivor
FOR i from 0 to n-1:
    IF i == candidate: CONTINUE
    
    IF knows(candidate, i) OR NOT knows(i, candidate):
        RETURN -1

RETURN candidate
Worked Example:party [0, 1, 2], real celebrity 1
0
0
1
1
Candidate B
2
2
Candidate A
Check learns/knows relationship. Ask knows(2, 1): Returns true. Since 2 knows someone, 2 cannot be a celebrity. Discard 2, keep 1. Stack = [0, 1].
0
0
Candidate B
1
1
Candidate A
Ask knows(1, 0): Returns false. Since 1 does not know 0, 0 cannot be the celebrity (celebrity must be known by everyone). Discard 0, keep 1. Stack = [1].
0
1
Candidate
Candidate 1 remains. We now perform a verification pass: check that knows(1, 0) and knows(1, 2) are false (1 knows no one), and knows(0, 1) and knows(2, 1) are true (everyone knows 1). All checks pass! Return 1.
Interactive Strategy Visualization
ELIMINATION TOURNAMENT INSIGHT

The Celebrity Problem Strategy

P0
P1
P2
Initial Stack

Mental Model

If A knows B, A cannot be the celebrity.

If A don't know B, B cannot be the celebrity.

LOGICSTEP 1/5
Start with all people on a stack. We need to find the one potential candidate.
TIP

O(N) Complexity

Instead of an O(N²) matrix scan, the elimination tournament strategy finds the truth in linear time by removing one person from contention in every comparison!

O(N²) Ask Every Pair
→
O(N) Eliminate Then Verify