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

Find a Celebrity from a Knows Matrix

Hints

1. Compare candidates pairwise so each matrix lookup eliminates one person.
2. The last possible candidate still needs a full incoming and outgoing verification pass.

Approach

Keep one candidate. Comparing the candidate with each later person eliminates one of them: if the candidate knows that person, the candidate cannot be a celebrity, so replace it; otherwise that later person cannot be a celebrity. After one pass, only one possible candidate remains. Verify both required directions against every other person, ignoring the diagonal. Return the candidate only if it knows nobody else and everybody else knows it; otherwise return -1. Elimination and verification each use linear lookups and constant state.

• Time complexity: O(n) matrix lookups.
• Space complexity: O(1) auxiliary space.