The celebrity problem

Medium

Problem

At a party of n people, a celebrity is someone everyone knows but who knows nobody. M[i][j] = 1 means person i knows person j. Return the celebrity's index, or −1 if there is none. Aim for O(n).

Example 1

Input:  M = [[0,1,0], [0,0,0], [0,1,0]]
Output: 1

Everyone knows person 1, and person 1 knows nobody.

Also asked as: The celebrity Problem

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Elimination with a stack / two pointers

Time O(n)Space O(1)

Push everyone; repeatedly pop two — if a knows b, a is not the celebrity (keep b), else keep a. One candidate remains; verify they know nobody and everybody knows them.

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