In a party of n people, a celebrity is someone whom everyone else knows but who knows no one else. You are given an n x n matrix mat where mat[i][j] = 1 means person i knows person j (and 0 otherwise).
Return the index of the celebrity, or -1 if there is none.
Input: mat = [[0,1,0],[0,0,0],[0,1,0]] Output: 1 Person 1 knows no one and is known by 0 and 2, so 1 is the celebrity.
Input: mat = [[0,1],[1,0]] Output: -1 Each knows the other, so neither knows no one — there is no celebrity.
- 1 <= n <= 3000 - mat[i][j] is 0 or 1 - mat[i][i] = 0
Checking every person against everyone is O(n²). But one comparison eliminates a person: if A knows B, then A can't be the celebrity (a celebrity knows no one); if A doesn't know B, then B can't be the celebrity (everyone knows a celebrity). So a single left-to-right sweep narrows n candidates down to one, which you then verify — all in O(n) comparisons.
“Does a celebrity know themselves?”
The diagonal is ignored; a celebrity knows no other person.
“Can there be more than one celebrity?”
No — at most one, since a second celebrity would have to be known by (and thus 'known' isn't reciprocated by) the first.
Each knows-query eliminates one person: if the candidate knows someone, the candidate is out; otherwise that someone is out.
So I sweep once, keeping a single surviving candidate.
Then I verify that candidate knows no one and is known by all — O(n) total comparisons.
Worked example — 3 people, mat = [[0,1,0],[0,0,0],[0,1,0]]
elimination: cand=0; mat[0][1]=1 -> cand=1; mat[1][2]=0 -> cand stays 1 verify 1: knows no one? mat[1][0]=0, mat[1][2]=0 yes; known by all? mat[0][1]=1, mat[2][1]=1 yes celebrity = 1
mat[A][B] == 1 rules out A (a celebrity knows nobody); mat[A][B] == 0 rules out B (everyone knows a celebrity). Either way, one candidate falls.
Starting from person 0 and eliminating one per step reduces n candidates to a single survivor in n-1 comparisons.
The survivor is only a possible celebrity; you must confirm it knows no one and is known by all, or return -1.
| Check everyone | Eliminate then verify | |
|---|---|---|
| Idea | For each person, test knows-none and known-by-all | Sweep to one candidate, then verify |
| Time | O(n^2) | O(n) |
| Space | O(1) | O(1) |
Full code is in the Approaches selector below.
Key takeaway
Each knows-query eliminates one person, so one left-to-right sweep narrows n candidates to a single survivor in O(n). Verify that survivor knows no one and is known by all; return it, or -1 if verification fails.
cand = 0 for i in 1 .. n-1: if mat[cand][i] == 1: cand = i for i in 0 .. n-1: if i != cand and (mat[cand][i] == 1 or mat[i][cand] == 0): return -1 return cand
