The Celebrity Problem

Problem Among N people, a celebrity is known by everyone but knows no one. Given the relation as an N x N matrix or a knows(a, b) API, find the celebrity or report none exists.

Input / Output

• Input: N and knows(a, b) → bool.
• Output: celebrity index, or -1.

Constraints

• O(N) calls to knows expected — the O(N^2) full-matrix scan is the brute force to beat.

Example

• M = [[0,1,0],[0,0,0],[0,1,0]] → person 1 (row of zeros, column of ones).

Expected approach

• Elimination: keep a candidate c starting at 0; for each i, if knows(c, i) then c = i (c can't be a celebrity; i still can). One pass leaves a single candidate; verify it with a second pass (knows(c, i) false for all i, knows(i, c) true for all i ≠ c). 3N calls total → O(N) time, O(1) space. The stack formulation (push all, pop pairs, eliminate one) is equivalent.