LeetCode #277 Medium

Find the Celebrity

Among n people, a celebrity is known by everyone and knows no one. Find them with O(n) knows(a,b) queries, or return −1.

two-pointersgraphelimination

Open on LeetCode ↗

02

Intuition

One question eliminates one person: if a knows b, a isn't a celebrity; if not, b isn't. Run one elimination pass to leave a single candidate, then verify them with 2n more queries.

How to spot this pattern

When every pair could be queried but the answer is unique, look for a question whose answer eliminates one candidate whichever way it goes. knows(a, b) does exactly that: if true, a can't be the celebrity; if false, b can't. One pass of n−1 such questions leaves a single survivor, which you then verify. That eliminate-one-per-question idea is the whole technique.

03

Approach

1

Every query kills someone

knows(a,b) true → a is out (celebrities know nobody). False → b is out (everyone knows a celebrity). Either way one candidate drops.

2

Single survivor

Sweep i from 1..n−1 with a running candidate: if candidate knows i, i becomes the candidate. n−1 queries leave one possibility.

3

Verify

The elimination proves nobody else can be the celebrity, not that the survivor is. Check the survivor knows no one and everyone knows them.

04

Solution & live demo

▶1def find_celebrity(n, knows):
▶2    cand = 0
▶3    for i in range(1, n):
▶4        if knows(cand, i):
▶5            cand = i
▶6    for i in range(n):
▶7        if i != cand and (knows(cand, i) or not knows(i, cand)):
▶8            return -1
▶9    return cand

05

Common pitfalls

Skipping the verification pass

✗ Wrong

for i in range(1, n):
    if knows(cand, i): cand = i
return cand

✓ Right

for i in range(n):
    if i != cand and (knows(cand, i) or not knows(i, cand)):
        return -1
return cand

The first pass only proves that everyone else is disqualified — it never proves the survivor qualifies. When no celebrity exists, some candidate still survives, and returning it is wrong. The second pass is what distinguishes "last one standing" from "actually a celebrity".

Comparing the candidate against itself during verification

✗ Wrong

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

✓ Right

for i in range(n):
    if i != cand and (knows(cand, i) or not knows(i, cand)):
        return -1

knows(cand, cand) is undefined by the problem and typically returns False, so not knows(i, cand) fires and a genuine celebrity is rejected. The candidate must be excluded from its own check.

Checking every pair

✗ Wrong

for a in range(n):
    for b in range(n):
        ...

✓ Right

cand = 0
for i in range(1, n):
    if knows(cand, i): cand = i

That's O(n²) calls when O(n) suffices to find the candidate. Each query already rules someone out permanently, so re-asking about eliminated people is wasted work.

06

Edge cases

No celebrity exists

Verification fails → −1. The elimination pass alone can't detect this.

n = 1

Sole person is trivially the celebrity — verification passes vacuously.

07

Complexity

Time

O(n)

Space

O(1)

≤ 3n−3 knows() calls.