Skip to main content
Talentd

Find the Celebrity - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersGraphInteractive6 min readAsked at: Amazon, Microsoft, Apple +9
Practice this problem

Problem Statement

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].length
  • 2 <= n <= 100
  • graph[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?

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Degree CountingO(n²)O(n)When modeling the problem as a graph and clarity is preferred over efficiency
Stack Candidate EliminationO(n)O(n)When using pairwise elimination logic and stack structures
Two-Pointer Candidate ScanO(n)O(1)Optimal interview solution with minimal API calls and constant memory

Video Solution

Find the Celebrity • Kevin Naughton Jr. • 41,920 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Celebrity easy or hard?
Find the Celebrity is typically rated medium difficulty. The brute force idea is simple, but recognizing the elimination strategy that reduces the problem to O(n) comparisons requires deeper insight.
Find the Celebrity Python/Java solution
Most implementations follow the same structure across languages. First identify a candidate in one pass using the knows API, then verify the candidate with two checks: they know no one and everyone knows them. This pattern translates directly to Python, Java, C++, and Go.
How to solve Find the Celebrity in O(n)?
Keep a single candidate and iterate through people from 1 to n-1. If the current candidate knows person i, update the candidate to i because a celebrity cannot know anyone. After the scan, verify the candidate by ensuring they know nobody and everyone knows them. This uses O(n) API calls and constant space.
What is the best approach for Find the Celebrity?
The optimal approach is candidate elimination using a single pass. Maintain a potential celebrity and eliminate people based on the knows(a,b) relation. After the pass, verify the candidate by checking they know nobody and everyone knows them. This solution runs in O(n) time and O(1) space.
Is Find the Celebrity asked at Google/Amazon/Meta?
Find the Celebrity is a classic interview problem frequently associated with companies like Google and Meta because it tests elimination logic and API-based reasoning. The problem also appears in discussions about minimizing queries in interactive systems.
What data structure is used in Find the Celebrity?
The problem can be viewed as a directed graph where edges represent the knows relationship. Practical solutions often use simple pointers or a stack for candidate elimination rather than storing the full graph.
What is the time complexity of Find the Celebrity?
The optimal algorithm runs in O(n) time because each comparison eliminates one potential candidate. A second pass verifies the candidate in another O(n) checks. Brute force solutions require O(n^2) API calls since they test every pair of people.

Ready to solve this problem?

Practice Find the Celebrity with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Town Judge