Celebrity Problem
HardEach question eliminates one person
Problem
In a party of n people, a celebrity is known by everyone but knows no one. Find the celebrity (or -1).
Eliminate: if A knows B, A isn't the celebrity; one candidate survives, then verify them.
The idea
Ask whether a knows b: if yes, a cannot be the celebrity, and if no, b cannot be. Either way one candidate is eliminated per question, so a single pass leaves one candidate that a final verification pass confirms.
The trick
- n-1 questions to find the candidate, then 2n to verify.
- Verification is mandatory — elimination alone does not prove celebrity status.
- O(n) queries, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — knows matrix Values: 0.
1cand=02for i in 1..n-1: if knows(cand,i): cand=i3verify cand knows no one and everyone knows candInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- knows = [[0,1,0],[0,0,0],[0,1,0]]
- Output:
- 1
- Explanation:
- Person 1 is known by all and knows nobody.
Example 2
- Input:
- knows = [[0,1],[1,0]]
- Output:
- -1
- Explanation:
- They know each other → no celebrity → -1.
Example 3
- Input:
- knows = [[0]]
- Output:
- 0
- Explanation:
- One person is trivially the celebrity.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.