The Celebrity Problem | Problems

In a party of N people, a celebrity is someone known by everyone but knows no one. Given a knows(a, b) function, find the celebrity or return -1.

Example: N=3, matrix=[[0,1,0],[0,0,0],[0,1,0]] → celebrity = 1

Sample Input

—

Sample Output

—

Constraints

2 <= n <= 500

Topics

Stack&Queue

Two Pointer Elimination

function findCelebrity(n, knows) {
  let candidate = 0;
  for (let i = 1; i < n; i++) if (knows(candidate, i)) candidate = i;
  for (let i = 0; i < n; i++) {
    if (i === candidate) continue;
    if (knows(candidate, i) || !knows(i, candidate)) return -1;
  }
  return candidate;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.