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).