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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(1)

≤ 3n−3 knows() calls.