The celebrity problem
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.
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;}