Leetcode 277. Find the Celebrity
Problem Explanation
You are given a list of n people represented as an adjacency matrix where a[i][j] = 1 means person i knows person j and a[i][j] = 0 means person i doesn't know person j.
Among these n people, there may be a celebrity who is recognized by everyone but doesn't know anyone else. Your task is to find the celebrity if one exists, otherwise return -1. The only type of question you can ask is "Hi, A. Do you know B?" to find out if person A knows person B.
Your task is to implement a function findCelebrity(n)
which would identify the celebrity (if he/she is in the party) by asking as few questions as possible.
Approach
The solution uses a two-pass approach to find the celebrity.
-
In the first pass, we iterate through each person i where each person is assumed to be the celebrity. We check whether the current celebrity knows the next person i. If they do, that means they are not a celebrity and therefore the candidate for celebrity is updated to the person i. This happens because a celebrity doesn't know anybody else. This pass assures that if there is a celebrity, he/she would be among the last person to be checked.
-
After the first pass, we need to do a second check to verify that the candidate is actually a celebrity. For all people i, if candidate knows any person i or any person i doesn't know candidate, return -1 as that indicates that the candidate is not a celebrity.
-
If we get through the second check without returning -1, that means the candidate is the celebrity and we return his/her id.
Python Solution
1 2python 3class Solution: 4 def findCelebrity(self, n): 5 candidate = 0 6 for i in range(1, n): 7 if knows(candidate, i): # First check to find the last person acknowledged by everyone. 8 candidate = i 9 10 for i in range(n): 11 if (i != candidate) and (knows(candidate, i) or not knows(i, candidate)): # Second check to verify that the candidate doesn't know anyone and everyone knows candidate. 12 return -1 13 return candidate
Java Solution
1
2java
3public class Solution {
4
5 public int findCelebrity(int n) {
6
7 int candidate = 0;
8
9 for (int i=0; i<n; i++) { // First check to find the last person acknowledged by everyone.
10 if (knows(candidate, i)) {
11 candidate = i;
12 }
13 }
14
15 for (int i=0; i<n; i++) { // Second check to verify that the candidate doesn't know anyone and everyone knows candidate.
16 if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) {
17 return -1;
18 }
19 }
20 return candidate;
21 }
22}
JavaScript Solution
1
2javascript
3var Solution = function() {
4
5 var findCelebrity = function(n) {
6 var candidate = 0;
7 for (var i = 0; i < n; i++) { // First check to find the last person acknowledged by everyone.
8 if (knows(candidate, i)) {
9 candidate = i;
10 }
11 }
12 for (var i = 0; i < n; i++) {
13 if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) { // Second check to verify that the candidate doesn't know anyone and everyone knows candidate.
14 return -1;
15 }
16 }
17 return candidate;
18 }
19};
C++ Solution
1
2c++
3class Solution {
4public:
5 int findCelebrity(int n) {
6 int candidate = 0;
7 for (int i = 0; i < n; i++) { // First check to find the last person acknowledged by everyone.
8 if (knows(candidate, i)) {
9 candidate = i;
10 }
11 }
12 for (int i = 0; i < n; i++) {
13 if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) { // Second check to verify that the candidate doesn't know anyone and everyone knows candidate.
14 return -1;
15 }
16 }
17 return candidate;
18 }
19};
C# Solution
1
2csharp
3public class Solution {
4
5 public int findCelebrity(int n) {
6 int candidate = 0;
7 for (int i = 0; i < n; i++) { // First check to find the last person acknowledged by everyone.
8 if (knows(candidate, i)) {
9 candidate = i;
10 }
11 }
12
13 for (int i = 0; i < n; i++) { // Second check to verify that the candidate doesn't know anyone and everyone knows candidate.
14 if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) {
15 return -1;
16 }
17 }
18 return candidate;
19 }
20}
In all of the above solutions, knows(a, b)
is an API provided by LeetCode to check if person a knows person b.In our provided solution, we used an elimination method to reduce our potential celebrity candidates with every iteration of the loop. As a result, the remaining candidate is always the last person who hasn't been eliminated as a celebrity.
However, it's worth remembering that even after we have identified a potential celebrity; we must confirm that this candidate knows no one and everyone knows them.
This solution has a time complexity of O(n). In the worst case scenario, the candidate is the last person, everyone else is compared with the candidate two times: 1) compared with the candidate 2) the candidate is compared with others. This gives us a rough estimation of 3n, which is simplified to O(n).
In conclusion, we have provided the solution to the problem in four most commonly used programming languages: Python, Java, JavaScript and C++. The key part to finding the solution is to realize that a celebrity is known by everyone but knows nobody. We conducted a two pass check: in the first pass, we determine a candidate who could be a potential celebrity; in the second pass, we validate this candidate. If the candidate passes the check, we return their id. Otherwise, we return -1 indicating no celebrity exists.
So next time you attend a party and suspect there might be a celebrity among you all, feel free to use these strategies to find them! Who knows? Maybe you'll be partying with a celebrity! But don't get your hopes up. After all, celebrities are as rare in real life as they are in this problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.