Find a Celebrity from a Knows Matrix

Problem

Among n people, a celebrity knows nobody else and is known by everybody else. Determine the celebrity's index, or return -1 if no celebrity exists.

Function Contract

Implement find_celebrity(knows), where knows[a][b] is true exactly when person a knows person b.

Rules

• A person's diagonal entry is irrelevant.
• A valid celebrity c satisfies knows[c][i] == false and knows[i][c] == true for every i != c.
• Return -1 rather than an unverified candidate.
• Use O(1) auxiliary space beyond the input.

Constraints

• 0 <= n <= 10000.
• The matrix is square.
• Target O(n) matrix lookups rather than checking every ordered pair.

Examples

knows = [
 [false, true, true],
 [false, false, true],
 [false, false, false]
]
output = 2