246. Find the Celebrity
A party has n guests labeled 0 through n - 1. A celebrity is a guest whom all n - 1 others know, while the celebrity knows none of them. There is at most one such guest.
You are given the full acquaintance table as an n × n matrix M of 0s and 1s, where M[i][j] = 1 means guest i knows guest j (knowing is one-directional). The diagonal entries M[i][i] are always 1 and carry no information — ignore them. When n = 1, the lone guest counts as the celebrity.
Return the celebrity's label, or -1 if the party has none.
The classic version of this puzzle hides the table behind a knows(a, b) oracle and scores you on how few questions you ask — aim for a solution that consults the relation only O(n) times.
Example 1:
Input: n = 3, M = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: Guests 0 and 2 both know guest 1 (column 1 is all 1s), and guest 1 knows neither of them (row 1 is 0 off the diagonal), so guest 1 is the celebrity.
Example 2:
Input: n = 3, M = [[1,1,0],[0,1,1],[1,0,1]]
Output: -1
Explanation: Knowing runs in a cycle 0 → 1 → 2 → 0, so every guest knows somebody — nobody qualifies.
Constraints:
- 1 ≤ n ≤ 500
- M[i][j] is 0 or 1
- M[i][i] = 1 for every i (ignore the diagonal)
- At most one celebrity exists.
Hints:
A single lookup eliminates one of two people: if a knows b, then a cannot be the celebrity; if a does not know b, then b cannot be (a celebrity is known by everyone).
Sweep once keeping a single survivor: start with guest 0 as the candidate and replace the candidate with i whenever the candidate knows i. After the sweep only that survivor can possibly be the celebrity — verify their row and column with one more pass, and return -1 if the check fails.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3, M = [[1,1,0],[0,1,0],[1,1,1]]
Expected output: 1