277. Find the Celebrity
Problem Description
The given problem presents a scenario where you're at a party with n
people, each labeled with a unique number between 0
and n - 1
. Your goal is to identify a possible celebrity among them. A celebrity is defined by two conditions: first, every other person at the party knows the celebrity, and second, the celebrity does not know anyone else at the party.
Your tool is a function knows(a, b)
, which checks if person a
knows person b
. You need to use this function to determine who, if anyone, is the celebrity at the party. It is important to minimize the number of calls to the knows
function, since your objective is to find the celebrity efficiently.
The output of your task is to return the unique label of the celebrity if one exists, or -1
if there is no celebrity present.
Intuition
To solve this problem, we take advantage of the unique characteristics of the celebrity:
- Every person other than the celebrity must know the celebrity, which means if
knows(a, b)
istrue
,a
cannot be the celebrity. - The celebrity does not know anyone else, which implies if
knows(a, b)
isfalse
,b
cannot be the celebrity.
Based on these points, we can iterate through the list of people at the party and use the knows
function to determine potential candidates for being the celebrity. One way to find the celebrity is to assume the first person (labeled 0
) is the celebrity and then check this assumption against every other person using knows
. If the assumed celebrity knows another person, then the assumption is wrong, and the other person becomes the new candidate for the celebrity. This process continues until we finish checking everybody.
After we find a candidate through the first iteration, we need to verify two conditions to confirm the candidate is indeed the celebrity:
- The candidate does not know any person. If the candidate knows any person, then the candidate cannot be the celebrity.
- Every person knows the candidate. If there is any person who does not know the candidate, then the candidate cannot be the celebrity.
The iteration for verification ensures that these conditions are met. If both conditions are satisfied for the candidate, then the candidate is the celebrity. Otherwise, there is no celebrity at the party.
The solution capitalizes on these ideas, using the intuition that knowing a person instantly disqualifies one from being a celebrity and not being known by at least one person also leads to a disqualification.
Learn more about Graph and Two Pointers patterns.
Solution Approach
The implementation provided is a straightforward two-pass solution that uses a simple elimination approach to find the celebrity.
First Pass - Identifying a Celebrity Candidate:
In the first for
loop, we start with an assumption that person 0
might be the celebrity. We iterate over the range from 1
to n
. For each person i
, we check if the current candidate (ans
) knows person i
using the knows(ans, i)
function.
- If
knows(ans, i)
istrue
, it means thatans
cannot be the celebrity because a celebrity does not know anyone else. So we update theans
to bei
sincei
is now a possible celebrity candidate. - If
knows(ans, i)
isfalse
, we do nothing and move on. This is becauseans
still could be the celebrity, as not knowingi
aligns with the definition of a celebrity.
By the end of this loop, the variable ans
holds the label of the only person who could potentially be the celebrity, because anyone who was known by ans
has been eliminated from contention.
Second Pass - Validating the Candidate:
Next, we perform a second for
loop to verify that the candidate (held in ans
) is indeed the celebrity. There are two checks we need to pass:
- The candidate should not know any other person. This is checked by
if knows(ans, i)
, whereans
is the candidate andi
is any other person's label. If the candidate knows any personi
, we return-1
as this disqualifies them from being the celebrity. - Every other person must know the candidate. We check this by ensuring
not knows(i, ans)
isfalse
, meaning personi
knowsans
. If we find someone who doesn't knowans
, we return-1
as this also disqualifiesans
from being the celebrity.
If both conditions are satisfied for all other people at the party, then we can safely conclude that ans
is the celebrity and return their label. If either condition fails for any person, we return -1
to indicate that there is no celebrity.
There is no need for any additional data structure as we can keep track of the potential celebrity with a single variable ans
. This approach is efficient because it requires at most 2*(n - 1)
calls to knows
— once to eliminate non-celebrities and once again to confirm that the remaining candidate is indeed the celebrity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example with 4 people at the party, where the unique labels for them are 0
, 1
, 2
, and 3
. Assume that person 3
is the celebrity according to the problem's definition. We want to identify this person using the solution approach described.
-
First Pass - Identifying a Celebrity Candidate:
- Initialize the candidate to person
0
(ans = 0). We'll check if person0
is the celebrity. - Check if
0
knows1
, usingknows(0, 1)
. Let's say it returnsfalse
, so we do nothing because0
could still be the celebrity. - Check if
0
knows2
, usingknows(0, 2)
. This time it returnstrue
, which means0
cannot be the celebrity. Update the candidate to person2
(ans = 2). - Check if
2
knows3
, usingknows(2, 3)
. It returnsfalse
, so we do nothing;2
is still a potential celebrity.
By the end of the first pass, our candidate is person
2
. - Initialize the candidate to person
-
Second Pass - Validating the Candidate:
- We need to verify if
2
is truly the celebrity by doing two checks: does not know anyone else (knows(ans, i)
) and is known by everyone else (knows(i, ans)
). - Check if
2
knows0
,1
, or3
, usingknows(2, 0)
,knows(2, 1)
, andknows(2, 3)
. They all should returnfalse
. Let's say they do, so2
passes the first check. - Next, we need to check if all others (
0
,1
,3
) know2
. We checkknows(0, 2)
,knows(1, 2)
, andknows(3, 2)
. They all should returntrue
for2
to be the celebrity. Let's sayknows(0, 2)
istrue
,knows(1, 2)
istrue
, butknows(3, 2)
isfalse
because the celebrity (3
) should not know anyone else.
Person
2
fails the second check because the celebrity (3
) does not know them.We will need to continue the same check for other persons
0
and1
:- Person
0
knows2
, so0
is not a celebrity. - Person
1
knows2
, so1
is not a celebrity.
Finally, when it comes to person
3
, the checks are as follows:3
does not know0
,1
, or2
, fulfilling the first condition of being a celebrity.- All persons
0
,1
, and2
know3
, fulfilling the second condition.
By the end of the verification process, we determine that person
3
meets both conditions, and since no other person does, we conclude that the label of the celebrity is3
. If the checks had failed for3
as they did for2
, then we would return-1
, indicating no celebrity is present. However, in this case, we return3
as the label of the celebrity at the party. - We need to verify if
Solution Implementation
1# The knows API is already defined for you.
2# Returns a boolean, indicating whether person a knows person b.
3# def knows(a: int, b: int) -> bool:
4
5class Solution:
6 def findCelebrity(self, n: int) -> int:
7 # Initialize the candidate for celebrity to 0
8 candidate = 0
9 # Iterate over the range from 1 to n-1
10 for i in range(1, n):
11 # If the candidate knows person i, then switch candidate to i
12 if knows(candidate, i):
13 candidate = i
14
15 # Verify candidate is indeed a celebrity
16 for i in range(n):
17 # Make sure we skip comparing the candidate with themselves
18 if candidate != i:
19 # Candidate should not know anyone, and everyone should know the candidate
20 if knows(candidate, i) or not knows(i, candidate):
21 # If the condition fails, return -1 because there is no celebrity
22 return -1
23
24 # If all checks pass, return the candidate as the celebrity
25 return candidate
26
1/* The knows API is defined in the parent class Relation.
2 boolean knows(int a, int b); */
3
4public class Solution extends Relation {
5 /**
6 * Determine the celebrity by knockout method
7 *
8 * @param n Number of people in the party
9 * @return The index of the celebrity if exists, otherwise return -1
10 */
11 public int findCelebrity(int n) {
12 // Initial assumption: the first person (0) may be the celebrity
13 int candidate = 0;
14
15 // First Pass: Find a candidate for celebrity
16 for (int i = 1; i < n; ++i) {
17 // If the candidate knows i, candidate cannot be a celebrity, thus i might be
18 if (knows(candidate, i)) {
19 candidate = i;
20 }
21 }
22
23 // Second Pass: Verify the candidate is really a celebrity
24 for (int i = 0; i < n; ++i) {
25 // Skip if i is the same as the candidate
26 if (candidate != i) {
27 // If the candidate knows i, or i doesn't know the candidate,
28 // then the candidate cannot be a celebrity
29 if (knows(candidate, i) || !knows(i, candidate)) {
30 return -1;
31 }
32 }
33 }
34
35 // If all checks pass, the candidate is a celebrity
36 return candidate;
37 }
38}
39
1/* The knows API is defined for you.
2 bool knows(int a, int b); */
3
4class Solution {
5public:
6 // This method is to find the celebrity within 'n' people.
7 // A celebrity is defined as somebody who everyone knows but who knows nobody themselves.
8 int findCelebrity(int n) {
9 // Initialize the candidate for celebrity to 0
10 int candidate = 0;
11
12 // The first loop is to find a candidate who might be the celebrity.
13 for (int i = 1; i < n; ++i) {
14 // If the candidate knows 'i', then 'candidate' can't be a celebrity.
15 // 'i' might be the celebrity.
16 if (knows(candidate, i)) {
17 candidate = i;
18 }
19 }
20
21 // The second loop is to confirm whether the candidate is the celebrity.
22 for (int i = 0; i < n; ++i) {
23 // The candidate should not know any other person,
24 // and all other people should know the candidate.
25 // If these conditions are not met, return -1 indicating no celebrity.
26 if (candidate != i && (knows(candidate, i) || !knows(i, candidate))) {
27 return -1;
28 }
29 }
30
31 // If all conditions are met, return the candidate as the celebrity.
32 return candidate;
33 }
34};
35
1// TypeScript function representing the knows API
2// It should return true if person a knows person b, false otherwise.
3declare function knows(a: number, b: number): boolean;
4
5// This function finds the celebrity within 'n' people.
6// A celebrity is someone whom everyone knows but who knows no one themselves.
7function findCelebrity(n: number): number {
8 // Initialize the candidate for the celebrity to 0
9 let candidate: number = 0;
10
11 // The first loop is to find a candidate who might be the celebrity.
12 for (let i = 1; i < n; i++) {
13 // If the candidate knows 'i', then 'candidate' cannot be the celebrity.
14 // In this case, 'i' might be the new candidate.
15 if (knows(candidate, i)) {
16 candidate = i;
17 }
18 }
19
20 // The second loop is to confirm whether the candidate is the celebrity.
21 for (let i = 0; i < n; i++) {
22 // The candidate should not know any other person,
23 // and all other people should know the candidate.
24 // If these conditions are not met, return -1 indicating there is no celebrity.
25 if (candidate !== i && (knows(candidate, i) || !knows(i, candidate))) {
26 return -1;
27 }
28 }
29
30 // If all conditions are met, return the candidate as the celebrity.
31 return candidate;
32}
33
Time and Space Complexity
Time Complexity
The given Python code is comprised of two separate for loops that are not nested.
The first for loop runs from 1 to n-1
and involves a constant amount of work for each iteration, i.e., one call to the knows
API function. This loop determines the candidate for the celebrity.
The second for loop checks whether the found candidate is actually a celebrity by making sure that everyone knows the candidate and the candidate knows no one (except themselves, which is not checked). This loop makes up to 2*(n-1)
calls to the knows
API.
Therefore, the time complexity for the code is O(n) + O(n)
, which simplifies to O(n)
.
Space Complexity
The code uses a fixed amount of extra space (only variable ans
is used to store the celebrity candidate). It does not allocate any space that is dependent on the input size n
.
Thus, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.