Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: "Hi, A. Do you know B?" to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given an integer n and a helper function bool knows(a, b) that tells you whether a knows b. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.
Return the celebrity's label if there is a celebrity at the party. If there is no celebrity, return -1.
Note that the n x n 2D array graph given as input is not directly available to you, and instead only accessible through the helper function knows. graph[i][j] == 1 represents person i knows person j, wherease graph[i][j] == 0 represents person j does not know person i.
Example 1:
Input: graph = [[1,1,0],[0,1,0],[1,1,1]] Output: 1 Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.
Example 2:
Input: graph = [[1,0,1],[1,1,0],[0,1,1]] Output: -1 Explanation: There is no celebrity.
Constraints:
n == graph.length == graph[i].length2 <= n <= 100graph[i][j] is 0 or 1.graph[i][i] == 1
Follow up: If the maximum number of allowed calls to the API knows is 3 * n, could you find a solution without exceeding the maximum number of calls?
Problem Overview: You are given n people at a party and access to an API knows(a, b) that returns whether person a knows person b. A celebrity is someone known by everyone else but who knows nobody. Your task is to identify that person or return -1 if no celebrity exists.
Approach 1: Brute Force Degree Counting (O(n²) time, O(n) space)
Model the party as a directed graph where an edge a → b means a knows b. The celebrity will have in-degree = n-1 and out-degree = 0. Iterate over every pair of people and call knows(a, b) to update incoming and outgoing counts. After processing all pairs, scan for a person satisfying the celebrity conditions. This approach is straightforward and demonstrates understanding of the graph interpretation, but it requires O(n²) API calls.
Approach 2: Stack Elimination (O(n) time, O(n) space)
Push all people onto a stack. Pop two candidates a and b and query knows(a, b). If a knows b, then a cannot be the celebrity, so push b back. Otherwise b cannot be the celebrity, so push a. Each comparison eliminates one candidate. After processing all pairs, one candidate remains. Perform a final verification pass to ensure this person knows nobody and everyone knows them. The elimination phase runs in O(n) time with O(n) stack space.
Approach 3: Two-Pointer Candidate Elimination (O(n) time, O(1) space)
The optimal method eliminates non-celebrities in a single pass using a candidate pointer. Start with candidate = 0. Iterate from person 1 to n-1. If candidate knows i, then the current candidate cannot be a celebrity, so update candidate = i. Otherwise i cannot be the celebrity. This works because a celebrity must never know anyone. After one pass, only one potential candidate remains. Perform a second pass verifying two conditions: the candidate knows nobody and everyone knows the candidate. The algorithm runs in O(n) time and O(1) space, commonly categorized under two pointers or elimination techniques in interactive problems.
Recommended for interviews: The two-pointer candidate elimination approach is what interviewers expect. The brute-force graph view shows you understand the celebrity definition using in-degree and out-degree, but the O(n) elimination strategy demonstrates algorithmic optimization and minimal API usage.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Degree Counting | O(n²) | O(n) | When modeling the problem as a graph and clarity is preferred over efficiency |
| Stack Candidate Elimination | O(n) | O(n) | When using pairwise elimination logic and stack structures |
| Two-Pointer Candidate Scan | O(n) | O(1) | Optimal interview solution with minimal API calls and constant memory |
Find the Celebrity • Kevin Naughton Jr. • 41,869 views views
Watch 9 more video solutions →Practice Find the Celebrity with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor