277 - Find the Celebrity

Difficulty: Medium | Pattern: Elimination / Two Pointers | Company tags: Amazon, Google, Facebook

Problem Statement

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. A celebrity is defined by:

1. Everyone knows the celebrity.
2. The celebrity knows nobody.

You have an API knows(a, b) which returns true if person a knows person b. Return the celebrity or -1 if there is none.

Constraint: Minimize the number of calls to knows.

Algorithm Flow

Approach: Elimination — O(n)

Key insight:

1. Find the candidate: iterate through people. If knows(candidate, i), the candidate cannot be a celebrity (celebrities know nobody) → update candidate to i.
2. Verify the candidate: check all others neither know the candidate as expected from the first rule.

def findCelebrity(n: int) -> int:
    candidate = 0
    
    # Find candidate
    for i in range(1, n):
        if knows(candidate, i):
            candidate = i
    
    # Verify candidate
    for i in range(n):
        if i == candidate:
            continue
        # Everyone must know candidate, candidate must know nobody
        if not knows(i, candidate) or knows(candidate, i):
            return -1
    
    return candidate

Dry Run

n=4, celebrity=2

Step 1 (find candidate):

i	knows(cand,i)	cand
0	start	0
1	knows(0,1)? No	0
2	knows(0,2)? Yes	2
3	knows(2,3)? No	2

Step 2 (verify 2):

• knows(0,2)? Yes ✓; knows(2,0)? No ✓
• knows(1,2)? Yes ✓; knows(2,1)? No ✓
• knows(3,2)? Yes ✓; knows(2,3)? No ✓

Return 2 ✓

Why O(n) Calls?

Step 1: n-1 calls. Step 2: 2(n-1) calls. Total: 3(n-1) = O(n).

Complexity

• Time: O(n) calls to knows
• Space: O(1)

Key Terms

Term	Definition
Elimination pattern	Repeatedly discard candidates that provably cannot satisfy a global property, leaving at most one survivor
Candidate	The single remaining person who could still be the celebrity after the elimination pass
Verification pass	A second linear scan confirming the candidate truly satisfies both celebrity conditions
API call minimization	Design goal of solving the problem using the fewest knows() queries, driving the two-pass O(n) structure

FAQ

1. Can this be solved without extra space? Yes — the algorithm only tracks a single candidate variable, giving O(1) space.
2. What if there is no celebrity? The verification pass catches this: if any person doesn't know the candidate, or the candidate knows someone, the function returns -1.
3. What if there are multiple people who look like celebrities? By problem definition at most one celebrity can exist (two people can't both be known-by-everyone-and-know-nobody unless n=1), so the elimination logic is safe.
4. What's the follow-up interviewers usually ask? "Can you do it in fewer than 3(n-1) calls?" — some implementations combine directions of the check to shave calls, or ask to generalize to weighted/partial "knows" relationships.
5. How would this change if knows(a, b) were expensive or asynchronous? You'd want to minimize and possibly batch/cache calls, reinforcing why the two-pass elimination (rather than checking all pairs, which is O(n^2)) is the expected optimization.

Quick Revision

• Celebrity: known by everyone, knows nobody — at most one such person can exist.
• Pass 1 (elimination): walk through people; whenever knows(candidate, i) is true, candidate can't be the celebrity, so switch candidate to i.
• After pass 1, only one candidate remains as a possibility — not yet proven.
• Pass 2 (verification): confirm every other person knows the candidate and the candidate knows nobody.
• Total calls: about 3(n-1), giving O(n) time and O(1) space.
• Brute force checking all pairs is O(n^2) and should be mentioned as the naive baseline.
• Edge cases: n=1 (that person is trivially the celebrity), and no celebrity exists at all.
• The elimination trick works because "knows" relationships let you safely discard non-candidates without missing the true celebrity.

Related Problems

• Two Pointers pattern problems in general (e.g., array partitioning by elimination) share the "discard non-candidates in one pass" idea.
• Majority Element (Boyer-Moore voting, LeetCode 169) — same elimination-then-verify structure applied to finding a majority value.
• Any "find the one valid X among N" problem where a single linear elimination pass narrows candidates before a verification pass.