The Celebrity Problem Hard 0 attempts
GeeksforGeeks ↗

The Celebrity Problem

Hard Stack&Queue GeeksforGeeks

At a party of N people, a celebrity is someone whom every other person knows, but who knows no one else themselves. Using a function knows(a, b) that tells you whether person a knows person b, identify the celebrity if one exists, or return -1 if there isn't one.

Input Format
Implement findCelebrity(n, knows). Inputs below show JavaScript function arguments; there is no stdin parsing. The fixture supplies a 0/1 matrix; the editor passes it as a knows(a,b) function.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
n = 3
knows = [[0,1,0],[0,0,0],[0,1,0]]
Output
1

Example 2

Input
n = 2
knows = [[0,1],[1,0]]
Output
-1
Constraints
  • 2 <= n <= 500
Test Cases (2)
Case 1
Args: [3,[[0,1,0],[0,0,0],[0,1,0]]] Expected: 1
Case 2
Args: [2,[[0,1],[1,0]]] Expected: -1
Topics
Stack&Queue

Two Pointer Elimination

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

JavaScript