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.

1. 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.

2. 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.

3. 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.