Quick Overview

Find a celebrity in a knows matrix with linear candidate elimination followed by complete verification that the candidate knows nobody and is known by everyone else.

Find a Celebrity from a Knows Matrix

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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 ```text knows = [ [false, true, true], [false, false, true], [false, false, false] ] output = 2 ```

Overview: Find a celebrity in a knows matrix with linear candidate elimination followed by complete verification that the candidate knows nobody and is known by everyone else.

Among n people, a celebrity knows nobody else and is known by everybody else. Given a square boolean matrix where knows[a][b] is true exactly when person a knows person b, return the celebrity's index or -1 if none exists. A person's diagonal entry is irrelevant. A valid celebrity c has knows[c][i] false and knows[i][c] true for every i different from c. Use constant auxiliary space and linear matrix lookups.

Constraints

  • 0 <= n <= 10000.
  • The knows matrix is square.
  • Diagonal entries are unrestricted and ignored.
  • A celebrity c must know nobody else and be known by everybody else.
  • Return -1 rather than an unverified candidate.

Examples

Input: ([[False, True, True], [False, False, True], [False, False, False]],)

Expected Output: 2

Explanation: This is the source example; person two knows nobody else and is known by both others.

Input: ([] ,)

Expected Output: -1

Explanation: No people means no celebrity.

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.

Loading coding console...

Show the approach

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.