The Celebrity Problem

Problem Statement

The celebrity problem goes like this: you go to a party of $N$ people, and you have to find out the celebrity over there.

According to the problem, the definition of celebrity is -- A celebrity is a person who is known to everyone in a party, but he does not knows anyone over there.

You will be given a square matrix $M[][]$ with dimensions N X N. The matrix $M[][]$ represents the people in the party. If an element of row $i$ and column $j$ is set to 1, then it means that the $i^{\text{th}}$ person knows the $j^{\text{th}}$ person. Please note that, here the $M[i][i]$ will always be 0.

Rule: A celebrity is known to everyone, but he does not know anyone at the party.

Input Format: You will be given a matrix M, where the elements in the matrix represent whether a person is known to another person or not. If the person is known to another person then, $M[i][j] = 1$, else it is equal to 0.

Task: Your task is to find out the celebrity at the party. Print the id of the celebrity, if present. If there is no celebrity at the party, then print -1.

Example

Example 1: Input:

Output:

Explanation: The person with id = 1 does not know anyone, hence there are all 0's marked in its row, whereas, all the other people know the person 1. Please note, there is 1 marked at $M[0][1] = M[2][1]$.

Example 2: Input:

Output:

Explanation: Both of the person know each other in the party, so there is no celebrity in the party.

Constraints

The constraints for the problem is given below :- Constraints:

$2 <= N <= 3000$
$0 <= M[][] <= 1$

Approach 1: Brute Force

While thinking of the celebrity problem, the very first thought that comes up to your mind would be -- To find the one person in the matrix, who does not know anyone, or the whole row is filled with 0 signifying that he does not know anyone. However, this is not enough, because we also need to make sure that everyone knows the celebrity. So, our next target would be to ensure that everyone knows that one person, who does not knows anyone.

Well, this could be very easily done by following the below algorithm :-

Note: Please suppose that we are already provided with the "knows" function, that states whether a person knows another person or not!

Algorithm:

• Firstly, let us say we have our celebrity variable marked as -1, since we are yet to find the celebrity.
• After that, just run a loop $i$ that ranges through the length of the matrix -- that is from $0$ to $N-1$ and check whether it satisfies the condition of being a celebrity or not.
  • Let us have two variables knows_anyone and everyone_knows that serve the purpose of checking whether the element is a celebrity or not.
  • Run a loop in which, $j$ (say) ranges from $0$ to $N-1$ and check knows[i][j] is false for all the value of $M[i][j]$. In that case, set knows_anyone to false.
  • Again, run a loop, where $j$ (say) ranges from $0$ to $N-1$ and check if knows[i][j] returns a true for all the values of $j$, except when $j=i$, then set everyone_knows to True.
• If the value of knows_anyone is False and everyone_knows is True, then this is our celebrity. Hence assign the value of $i$ to celebrity and break.
• Finally, return the celebrity.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code for the above brute force approach.

Java Implementation

Below given is the Java code for the above brute force approach.

Code:

Python Implementation

Below given is the Python code for the above brute force approach.

Code:

Time Complexity Analysis

The time complexity for the brute force approach is $O(N*N)$, where $N$ is the number of person at the party.

Space Complexity Analysis

The space taken is constant for the given approach, this is because we are not using any data structure to store anything. Space Complexity: $O(1)$

Approach 2 - Using Graphs

The celebrity problem can also be represented in terms of the Graph Problem. We can think it as a directed graph which is having $N$ nodes which are numbered $0$ to $N-1$. If our function knows(i,j) returns a $True$, then that means, person $i$ knows the person $j$, an so, we can say that there is a directed edge from the node $i$ to the node $j$.

We may also conclude that, in case the celebrity is present in our array then, that particular node that will represent the celebrity will have $(n-1)$ ingoing node and $0$ outgoing node. That means the celebrity will be represented by a global sink.

Let us jolt down our algorithm to find the celebrity --

Algorithm:

• Firstly, initialize the celebrity with $-1$
• Create two arrays $Indegree$ and $Outdegree$, each of size $N$. Initialize both with 0's. These arrays will basically represent our indegree and outdegree of each node in the graph.
• Run a nested loop, the $i$ ranges from $0$ to $N-1$ and the inner loop -- $j$ ranges from $0$ to $N-1$. Now, for each pair of $M[i,j]$ check whether knows(i,j) returns $True$ or not. If it returns a $True$, then increment the $Outdegree$ by $1$ (because a node is directed from i to j), and also increment the $Indegree$ by $1$.
• Run another nested loop to find the element whose $Outdegree$ is $0$ and $Indegree$ is $N-1$.
• If such an element exists, then it is the celebrity. Otherwise, the celebrity remains $-1$.
• Return the celebrity.

Implementation in C++, Java and Python

C++ Code

Below given is the C++ code for the above approach using graphs.

Code:

Java Code

Below given is the Java code for the above approach using graphs.

Code:

Python Code

Below given is the Python code for the above approach using graphs.

Code:

Output:

Time Complexity Analysis

In the above approach of finding out the celebrity using the graphs method, we run two for loops to calculate our indegree and outdegree. Naturally, the time complexity becomes O($N^2$), where $N$ is the number of people in the celebrity problem.

Space Complexity Analysis

In the above problem, we are using two arrays for storing our indegree and outdegree of the graph. Hence, our space complexity becomes $O(N)+O(N)$, which can be approximated as $O(N)$, for $N$ number of person in the celebrity problem.

Approach 3 - Using Recursion

After deeply analyzing the problem, we find one pattern, that is, if anyhow we can eliminate $N-1$ the person in the party who is not the celebrity, then we can easily confirm if the last person is a celebrity or not. In simple words, if we can figure out a method that will work to find out whether or not $N-1$ people know each other or not, then we can definitely look out for the 1 person whether he is a celebrity or not.

And, this can be easily done by Recursion.

But hold on! based on what criteria will we eliminate the persons? So, as the problem already stated for us --

• If $X$ knows a person $Y$, then $X$ can never be a celebrity. But there is a "possibility" of $Y$ beign a celebrity
• On the other hand, if $Y$ knows $X$, then $Y$ can never be a celebrity, while $X$ still stands a chance of being one.

So, this information will be used to eliminate all the person who does not stand a chance of being a celebrity.

Finding our potential celebrity :

We could recursively call $N-1$ persons, while every time trying to check whether he is the celebrity or not. Our base case will be reached whenever we have 0 people, in that case, we would simply return -1, for obvious reasons (if there are 0 people, then no one can be the celebrity). Suppose, when we reach the $X^{\text{th}}$ step in the recursion, then we will be comparing the $X^{\text{th}}$ person with the rest of $(X-1)^{\text{th}}$ person, whether any of them know each other or not. If we have a potential celebrity till this step, then it will be returned by our recursion and might get a chance to be returned from our function.

So, in case our recursive function returns any id, instead of -1, then it stands a chance of being the celebrity. We could use the id to confirm whether the person with this id knows anyone or not. In case, it does not knows anyone, then voila! he's our celebrity.

Algorithm

• Firstly, we create our recursive function, that will return us our potential celebrity. This function will take $N$ as input, signifying the number of people in the party.
• If there are 0 person, then that becomes the base case for our recursive function and it will return a $-1$.
• Then, use the recursive function to come up with an id that knows or does not knows the $N-1$ person.
• Suppose, we have our helper function $knows(a,b)$ that will tell us whether a knows b or not. So, if the $id$ returned by the recursive function knows any of the $N-1$ people, then there is no chance that $id$ is a celebrity. However, there still stands a chance that one of the $N-1$ people can be a celebrity. So, when $knows(id,n-1)$ returns a true, we will return $N-1$ to our recursive function. So that it can try to find a celebrity among them.
• On the other hand, if we try to search for $knows(n-1,id)$ , and it returns a true, then it means the $N-1$ persons know the person with an id = $id$. So we will return this $id$ to our function.
• Finally we will check if $id$ returned by our recursive function is a celebrity or not.

Implementation in C++, Java & Python

C++ Code

Code:

Java Code

Python Code

Output:

Time Complexity Analysis

In the above approach of finding out the celebrity using the recursion method, the recursive function is called at most $N$ times. Naturally, the time complexity becomes $O(N)$, where $N$ is the number of people in the celebrity problem.

Space Complexity Analysis

Apart from the recursion stack space, there is no extra space used. Hence space complexity is $O(1)$.

Approach 4: Using Stack + Elimination Technique

If we carefully observe our requirements for the problem, the stack becomes a good candidate to solve this. Do you know why? Simply because we can use the stack coupled with the elimination technique to find out the potential celebrity. Finally, we can use our technique to ensure whether the potential celebrity is the real celebrity or not. Let us understand in-depth how will we do this.

Basically, the intuition behind this approach will be -- we will be adding all of the elements in the stack (from $0$ to $N-1$), and then everytime we will pop two elements from the stack and check whether they know each other or not. If an element does not know the other (then it can be our potential celebrity) we will push it back into the stack, and eliminate the other element. This will continue till there is only one element left into our stack.

Let us now see the algorithm for the stack and elimination technique:

1. Create a stack and put all the elements from $0$ to $N-1$ into the stack.
2. Run a while loop through the stack till we have only 1 element left in the stack. In the while loop ---
   1. Suppose, our popped elements are index $i$ and index $j$, where $i != j$ is mandatory
   2. Now, if $matrix[i][j] = 1$, then that means $i$ knows $j$, so push back $j$ into the stack, but not $i$. So, $i$ gets eliminated.
   3. Otherwise, if $matrix[j][i] = 1$, then push $i$ into the stack and eliminate $j$.
3. Now, our stack will have one element, say potential_celeb. Just check if the row of the stack is all 0 (except when col = potential_celeb) and the column of the stack is all one (except when row = potential_celeb) or not.
4. If the above condition satisfies, then return the answer as our celebrity of the problem. Else, no one is the celebrity and return -1

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ implementation of this approach.

Code:

Java Implementation

Below given is the Java implementation of this approach.

Code:

Python Implementation

Below given is the Python implementation of this approach.

Code:

Output:

Time Complexity Analysis

In the above approach of finding out the celebrity using the stack method, each time we are popping two elements and pushing back one of them. And we are doing this for $N$ times overall. So, the time complexity becomes $O(N)$. Also, at the end, we confirm whether our potential celebrity is a celebrity or not. For that, another $O(N)$ is required. But overall worst case complexity remains $O(N)$.

Space Complexity Analysis

Initially, we put all the elements into the stack, which took a space of $O(N)$. Hence, we may say the auxiliary space complexity is $O(N)$.

Approach 5: Two Pointer approach

So, let us end our celebrity problem, with one of the most popular approaches -- the two pointers approach. Till now we have used a lot of algorithms to solve this problem, but you are going to love this approach because it fits so well with the problem. In the last approaches, where we used to stack, graphs, recursion, etc. we saw every time in some or the other way some extra "space" was required, either the recursion stack space or we used some data structure to solve our problem. But, by using this approach, we are going to cut off that extra space too!! So, let us understand why does this approach become a celebrity of all the other approaches we discussed in this article.

Intuition behind the Two Pointers approach

The main intuition behind using this approach is that we can simply use two pointers here, one in the starting index of the matrix and another at the end. Suppose, we have two persons, $X$ and $Y$, if $X$ knows $Y$ then $Y$ is the celebrity or vice versa. Doing that, we will be left with only one person at the end of our loop. Finally, we will perform some more iterations to finally conclude whether the last person is the celebrity or not!!

Algorithm :

• First, declare i and j, where i = $0$ and j will be $n-1$
• Perform an iteration till i is less than j
• Now, check whether i knows j, in that case increment i, i.e. i = i + 1 (because i cannot be the celebrity)
• Else, if j knows i, then decrement j, i.e. j = j - 1
• Finally, the leftover index will be our potential celebrity.
• So, run a loop from $0 -> N-1$, and confirm whether the index is actually celebrity or not.

C++ Implementation

Below given is the C++ implementation of this approach.

Code:

Java Implementation

Below given is the Java implementation of this approach.

Code:

Python Implementation

Below given is the Python implementation of this approach.

Code:

Output:

Time Complexity Analysis

In the above approach of finding out the celebrity using the two pointers method, and at max we are iterating over n elements in our matrix to find the potential celebrity. Again we are iterating and checking whether the potential celebrity is the actual celebrity or not. Hence, the overall worst case time complexity becomes $O(N)$.

Space Complexity Analysis

We are not using any extra space in our code, except few variables. Hence, the overall space complexity becomes $O(1)$.