The Celebrity Problem Using Stack-Based Elimination

A celebrity is a person who is known by everyone but knows nobody. Given n people at a party, find the celebrity (if one exists) using the minimum number of questions.

Problem Definition

You have an n×n matrix knows[i][j] where knows[i][j] = 1 means person i knows person j. A celebrity:

• Is known by all other n-1 people
• Knows nobody

    0  1  2  3
0 [ 0, 0, 1, 0 ]
1 [ 0, 0, 1, 0 ]
2 [ 0, 0, 0, 0 ]  ← Celebrity (column all 1s except self, row all 0s)
3 [ 0, 0, 1, 0 ]

Brute Force — O(n²)

Check each person: verify their row is all 0s and their column is all 1s.

def find_celebrity_brute(knows, n):
    """Time: O(n²), Space: O(1)"""
    for candidate in range(n):
        is_celebrity = True
        for other in range(n):
            if candidate == other:
                continue
            if knows(candidate, other) or not knows(other, candidate):
                is_celebrity = False
                break
        if is_celebrity:
            return candidate
    return -1

Stack-Based Elimination — O(n)

The key insight: each knows(a, b) call eliminates one person.

• If knows(a, b) is True → a is NOT the celebrity (celebrities know nobody)
• If knows(a, b) is False → b is NOT the celebrity (everyone knows the celebrity)

Algorithm

1. Push all people onto a stack
2. Pop two, ask if one knows the other, eliminate one, push survivor back
3. After n-1 rounds, one candidate remains
4. Verify the candidate

def find_celebrity(knows, n):
    """
    Find celebrity using stack elimination.
    Time: O(n), Space: O(n)
    """
    stack = list(range(n))

    # Elimination phase: n-1 comparisons
    while len(stack) > 1:
        a = stack.pop()
        b = stack.pop()

        if knows(a, b):
            stack.append(b)  # a knows b, so a is not celebrity
        else:
            stack.append(a)  # a doesn't know b, so b is not celebrity

    candidate = stack[0]

    # Verification phase: 2(n-1) checks
    for i in range(n):
        if i == candidate:
            continue
        if knows(candidate, i) or not knows(i, candidate):
            return -1

    return candidate

Trace

People: 0, 1, 2, 3. Person 2 is the celebrity.

Stack: [0, 1, 2, 3]

Round 1: pop 3, 2 → knows(3,2)=True → 3 eliminated → push 2
  Stack: [0, 1, 2]

Round 2: pop 2, 1 → knows(2,1)=False → 1 eliminated → push 2
  Stack: [0, 2]

Round 3: pop 2, 0 → knows(2,0)=False → 0 eliminated → push 2
  Stack: [2]

Candidate: 2
Verify: row 2 is all 0s ✓, column 2 is all 1s ✓
Answer: 2

Two-Pointer Alternative

The same elimination logic works with two pointers — no stack needed:

def find_celebrity_two_pointer(knows, n):
    """Time: O(n), Space: O(1)"""
    left, right = 0, n - 1

    while left < right:
        if knows(left, right):
            left += 1
        else:
            right -= 1

    candidate = left

    for i in range(n):
        if i == candidate:
            continue
        if knows(candidate, i) or not knows(i, candidate):
            return -1

    return candidate

Proof of Correctness

Claim: The celebrity (if it exists) is never eliminated.

Proof: Suppose person C is the celebrity. When C is compared with any person X:

• knows(C, X) = False (C knows nobody), so X gets eliminated, C survives
• knows(X, C) = True (everyone knows C), so X gets eliminated, C survives

In either case, C survives. After n-1 eliminations, C must be the last one standing.

Complexity

Phase	Calls to knows()
Elimination	n - 1
Verification	2(n - 1)
Total	3(n - 1) = O(n)

Edge Cases

• No celebrity exists — verification phase catches this, returns -1
• n = 1 — the single person is trivially a celebrity
• Multiple people know nobody — at most one can be known by everyone

When to Use This Pattern

The elimination technique applies whenever you can discard one of two candidates per comparison. It appears in:

• Tournament-style algorithms
• Finding majority elements
• Voting algorithms (Boyer-Moore)

Related Problems

• Find the Town Judge (LeetCode 997) — graph degree version
• Majority Element (LeetCode 169) — Boyer-Moore voting
• Find the Winner of Circular Game (LeetCode 1823)