September 26, 2024

The Celebrity Problem

You go to a party of N people, and you have to find out the celebrity over there.

Scope

This article tells about how to solve celebrity problem.

In this article we will learn brute force approach to solve celebrity problem.

In this article we will learn to solve celebrity problem using graphs

In this article we will learn to solve celebrity problem using recursion.

Takeaways

Two Pointers approach is the most efficient way to solve the 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:

N = 3
M[][] = 
{{0 1 0},
{0 0 0}, 
{0 1 0}}

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:

N = 2
M[][] = 
{{0 1},
{1 0}}

Output:

-1

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, jj (say) ranges from 0 to N−1 and check knows[i][j] is false for all the value of M[i][j]M[i][j]. In that case, set knows_anyone to false.
- Again, run a loop, where jj (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.

// Brute Force Approach to find the celebrity

int findTheCelebrity(int n) {
    
    int celebrity = -1;

    // Run a loop through the length of the matrix
	// to check for the celebrity
    for(int i = 0; i < n; i++) {
        bool knows_anyone = false;
		bool everyone_knows = true;

        // Check whether person with id 'i' knows any other person.
        for(int j = 0; j < n; j++) {
			// suppose that the knows function is already implemented for us
            if(knows(i, j)) {
                knows_anyone = true;
                break;
            }
        }

        // Check whether perosn with id 'i' is known to all the other person.
        for(int j = 0; j < n; j++) {
            if(i != j and !knows(j, i)) {
                everyone_knows = false;
                break;
            }
        }

        if(!knows_anyone && everyone_knows) {
            celebrity = i;
            break;
        }
    }

    return celebrity;
}

Java Implementation

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

Code:

public class Solution {
	public static int findCelebrity(int n) {

        int celebrity = -1;

	    // Check one by one whether the person is a celebrity or not.
	    for(int i = 0; i < n; i++) {
	        boolean knows_anyone = false, everyoneKnows = true;

	        // Check whether perosn with id 'i' knows any other person.
	        for(int j = 0; j < n; j++) {
	            if(Runner.knows(i, j)) {
	                knows_anyone = true;
	                break;
	            }
	        }

	        // Check whether perosn with id 'i' is known to all the other person.
	        for(int j = 0; j < n; j++) {
	            if(i != j && !Runner.knows(j, i)) {
	                everyoneKnows = false;
	                break;
	            }
	        }

	        if(!knows_anyone && everyoneKnows) {
	            celebrity = i;
	            break;
	        }
	    }

	    return celebrity;
    }
}

Python Implementation

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

Code:

def findCelebrity(n, knows):
    celebrity = -1
    for i in range(0, n):
        knows_anyone = False
        everyone_knows = True

        # Check whether person with the id 'i' knows any other person or not
        for j in range(0, n):
            if knows(i, j) == True:
                knows_anyone = True
                break
        
        # Check whether person with the id 'i' is known to all the other person.
        for j in range(0, n):
            if i != j and knows(j, i) == False:
                everyone_knows = False
                break

        if knows_anyone == False and everyone_knows != False:
            celebrity = i
            break

    return celebrity

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, that person i knows the person j, and so, we can say that there is a directed edge from node i to 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 aTrue, then increment the Outdegree by 11 (because a node is directed from i to j), and also increment the Indegree by 11.
Run another nested loop to find the element whose Outdegree is 0 and IndegreeIndegree 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:


// C++ program to find the celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max number of persons in the party
#define N 8

// Person with 2 is celebrity
bool MATRIX[N][N] = {{0, 0, 1, 0},
					{0, 0, 1, 0},
					{0, 0, 0, 0},
					{0, 0, 1, 0}};

bool knows(int a, int b)
{
	return MATRIX[a][b];
}

// The function that finds the celebrity if present
// otherwise returns a -1
int findCelebrity(int n)
{
	//the graph needs not be constructed
	//as the edges can be found by
	//using knows function
	
	// the indegree and outdegree arrays
	int indegree[n]={0},outdegree[n]={0};
	
	//query for all edges
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			int x = knows(i,j);
			
			//set the degrees if there is an edge from i to j
			outdegree[i]+=x;
			indegree[j]+=x;
		}
	}
	
	//find a person with indegree n-1
	//and out degree 0, that person will be the celebrity
	for(int i=0; i<n; i++)
	if(indegree[i] == n-1 && outdegree[i] == 0)
		return i;
	
	return -1;
}

// Driver code
int main()
{
	int n = 4;
	int id = findCelebrity(n);
	id == -1 ? cout << "There is not celebrity" :
			cout << "Celebrity ID =  " << id;
	return 0;
}

Java Code

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

Code:

// Java program to find celebrity
import java.util.*;

class Main{
    // Max # of persons in the party
    static final int N = 8;
    
    // Person with 2 is celebrity
    static int MATRIX[][] = { { 0, 0, 1, 0 },
    						{ 0, 0, 1, 0 },
    						{ 0, 0, 0, 0 },
    						{ 0, 0, 1, 0 } };
    
    static int knows(int a, int b) { return MATRIX[a][b]; }
    
    // The function that finds the celebrity if present
    // otherwise returns a -1
    static int findCelebrity(int n)
    {
    
    	//we dont need to create the graph because
    	// the edges can be found by the knows() function
    	
    	// the indegree and outdegree arrays
    	int[] indegree = new int[n];
    	int[] outdegree = new int[n];
    
    	// query for all edges
    	for (int i = 0; i < n; i++)
    	{
    	for (int j = 0; j < n; j++)
    	{
    		int x = knows(i, j);
    
    		//set the degrees if there is an edge from i to j
    		outdegree[i] += x;
    		indegree[j] += x;
    	}
    	}
    
    	//find a person with indegree n-1
    	//and out degree 0, that person will be the celebrity
    	for (int i = 0; i < n; i++)
    	if (indegree[i] == n - 1 && outdegree[i] == 0)
    		return i;
    
    	return -1;
    }
    
    // Driver code
    public static void main(String[] args)
    {
    	int n = 4;
    	int id = findCelebrity(n);
    	if (id == -1)
    	System.out.print("There is not celebrity present");
    	else
    	System.out.print("Celebrity ID = " + id);
    }
}

Python Code

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

Code:

# Python3 program to find celebrity

# Max number of persons in the party
N = 8

# Person with 2 is celebrity
MATRIX = [ [ 0, 0, 1, 0 ],
		[ 0, 0, 1, 0 ],
		[ 0, 0, 0, 0 ],
		[ 0, 0, 1, 0 ] ]
			
# Returns whether there is an edge b/w 
# x and y
def knows(x, y):
	return MATRIX[x][y]

def findCelebrity(n):
	# we dont need to create the graph because
	# the edges can be found by the knows() function
	
	# the indegree and outdegree arrays
	indegree = [0 for x in range(n)]
	outdegree = [0 for x in range(n)]
	
	# Query for all edges
	for i in range(n):
		for j in range(n):
			x = knows(i, j)
			
			# set the degrees if there is an edge from i to j
			outdegree[i] += x
			indegree[j] += x
	
	# Find a person with indegree n-1
	# and out degree 0, that will be our celebrity
	for i in range(n):
		if (indegree[i] == n - 1 and
		outdegree[i] == 0):
			return i
			
	return -1
	
# Driver code
if __name__ == '__main__':
	
	n = 4
	id_celeb = findCelebrity(n)
	
	if id_celeb == -1:
		print("There is not celebrity present")
	else:
		print("Celebrity ID = ", id_celeb)

Output:

Celebrity ID =  2

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(N2), 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 Xth step in the recursion, then we will be comparing the Xth person with the rest of (X−1)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:

// C++ program to find the celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max number of persons in the party
#define N 8

// Person with ID = 1 is the celebrity
bool MATRIX[N][N] = { { 0, 1, 0, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 1, 0, 0 },
					{ 0, 1, 0, 0 } };

bool check_knows(int a, int b) { return MATRIX[a][b]; }


// Recursive function to find the celebrity
// If no one is the celebrity, returns -1, else
// returns the "probable celebrity" id
int findProbableCelebrity(int n)
{

	// The base case if n = 0, which means no person present
	// in that case ir returns 0, that is, no one is the celebrity
	if (n == 0)
		return -1;

	// the id returned by our Recursive function
	int idx = findProbableCelebrity(n - 1);

	// if there are no celebrities present
	if (idx == -1)
		return n - 1;


	// in case, "id" knows the nth person, then definitely
	// id is not the celebrity, however there is a chance
	// for the nth person to be one, so we return n-1
	else if (check_knows(idx, n - 1)) {
		return n - 1;
	}
	// in case, the "n-1" person knows the id person, then definitely
	// (n-1) is not the celebrity, however there is a chance
	// for the id person to be one, so we return id
	else if (check_knows(n - 1, idx)) {
		return idx;
	}

	// in case there is no celebrity
	return -1;
}

// checks whether the id returned from findProbableCelebrity
// is actually celebrity or not
int Celebrity(int n)
{
	// find the celebrity
	int id = findProbableCelebrity(n);

	// if id is -1 then no celebrity is present
	// so we simply return -1
	if (id == -1)
		return id;
	else {
		int c1 = 0, c2 = 0;

		// check whether id is celebrity or not
		for (int i = 0; i < n; i++)
			if (i != id) {
				c1 += check_knows(id, i);
				c2 += check_knows(i, id);
			}

		// if the id is known to every other
		// person in the party
		if (c1 == 0 && c2 == n - 1)
			return id;

		return -1;
	}
}

// Driver code
int main()
{
	int n = 4;
	int id = Celebrity(n);
	id == -1 ? cout << "No celebrity is present in the party"
			: cout << "Celebrity ID = " << id;
	return 0;
}

Java Code

// Java program for the above approach
import java.io.*;

class Main{
	// Max number of persons in the party
	static int N = 8;

	// Person with ID = 1 is the celebrity
	static int MATRIX[][] = { { 0, 1, 0, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 1, 0, 0 },
					{ 0, 1, 0, 0 } };;

	static int knows(int a, int b) { return MATRIX[a][b]; }

	// Recursive function to find the celebrity
// If no one is the celebrity, returns -1, else
// returns the "probable celebrity" id
	static int findProbableCelebrity(int n)
	{
		// The base case if n = 0, which means no person present
	// in that case ir returns 0, that is, no one is the celebrity
		if (n == 0)
			return -1;

		// the id returned by our Recursive function
		int id = findProbableCelebrity(n - 1);

		// if there are no celebrities present
		if (id == -1)
			return n - 1;

		// in case, "id" knows the nth person, then definitely
	// id is not the celebrity, however there is a chance
	// for the nth person to be one, so we return n-1
		else if (knows(id, n - 1) == 1) {
			return n - 1;
		}
		// in case, the "n-1" person knows the id person, then definitely
	// (n-1) is not the celebrity, however there is a chance
	// for the id person to be one, so we return id
		else if (knows(n - 1, id) == 1) {
			return id;
		}

		// in case there is no celebrity
		return -1;
	}

	// checks whether the id returned from findProbableCelebrity
// is actually celebrity or not
	static int Celebrity(int n)
	{
		// find the celebrity
		int id = findProbableCelebrity(n);

		// if id is -1 then no celebrity is present
	// so we simply return -1
		if (id == -1)
			return id;
		else {
			int c1 = 0, c2 = 0;

			// check whether id is celebrity or not
			for (int i = 0; i < n; i++)
				if (i != id) {
					c1 += knows(id, i);
					c2 += knows(i, id);
				}

			// if the id is known to every other
		// person in the party.
			if (c1 == 0 && c2 == n - 1)
				return id;

			return -1;
		}
	}

	// Driver code
	public static void main(String[] args)
	{
		int n = 4;
		int id = Celebrity(n);
		if (id == -1) {
			System.out.println("No celebrity is present in the party");
		}
		else {
			System.out.println("Celebrity ID " + id);
		}
	}
}

Python Code



# Python3 program to find celebrity

# Max number of persons in the party
N = 8

# Person with ID = 1 is the celebrity
MATRIX = [[0, 1, 0, 0],
		[0, 0, 0, 0],
		[0, 1, 0, 0],
		[0, 1, 0, 0]]


def knows(a, b):

	return MATRIX[a][b]

# Recursive function to find the celebrity
# If no one is the celebrity, returns -1, else
# returns the "probable celebrity" id


def findProbableCelebrity(n):

	# The base case if n = 0, which means no person present
	# in that case ir returns 0, that is, no one is the celebrity
	if (n == 0):
		return 0;

	# the id returned by our Recursive function
	idx = findProbableCelebrity(n - 1)

	# if there are no celebrities present
	if (idx == -1):
		return n - 1

	# in case, "id" knows the nth person, then definitely
	# id is not the celebrity, however there is a chance
	# for the nth person to be one, so we return n-1
	elif knows(idx, n - 1):
		return n - 1

	# in case, the "n-1" person knows the id person, then definitely
	# (n-1) is not the celebrity, however there is a chance
	# for the id person to be one, so we return id
	elif knows(n - 1, idx):
		return idx
	# in case there is no celebrity
	return - 1

# checks whether the id returned from findProbableCelebrity
# is actually celebrity or not
def Celebrity(n):

	# Find the celebrity
	idx=findProbableCelebrity(n)

	# if id is -1 then no celebrity is present
	# so we simply return -1
	if (idx == -1):
		return idx
	else:
		c1=0
		c2=0

		# check whether id is celebrity or not
		for i in range(n):
			if (i != idx):
				c1 += knows(idx, i)
				c2 += knows(i, idx)

		# if the id is known to every other
		# person in the party.
		if (c1 == 0 and c2 == n - 1):
			return idx

		return -1

# Driver code
if __name__ == '__main__':

	n=4
	idx=Celebrity(n)

	if idx == -1:
		print("No celebrity is present in the party")
	else:
		print("Celebrity ID", idx)

Output:

Celebrity ID = 1

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:

Create a stack and put all the elements from 0 to N−1 into the stack.
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!=ji!=j is mandatory
2. Now, if matrix[i][j]=1matrix[i][j]=1, then that means i know j, so push back j into the stack, but not i. So, i get eliminated.
3. Otherwise, if matrix[j][i]=1matrix[j][i]=1, then push i into the stack and eliminate j.
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.
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:

// C++ program to find celebrity
#include <bits/stdc++.h>
#include <list>
using namespace std;

// Max # of persons in the party
#define N 8

bool MATRIX[N][N] = { { 0, 0, 0, 1 },
							{ 0, 0, 0, 1 },
							{ 0, 0, 0, 1 },
							{ 0, 0, 0, 0 } };

bool knows(int a, int b)
{
	return MATRIX[a][b];
}

int findTheCelebrity(int n)
{
	// Our potential celebrity
	int Celeb;
	stack<int> stk;
	

	// Push all the elements into the stack
	for (int i = 0; i < n; i++)
		stk.push(i);

	// Find a potential celebrity
	while (stk.size() > 1)
	{ int x = stk.top();
		stk.pop();
		int y = stk.top();
		stk.pop();
		if (knows(x, y))
		{
		stk.push(y);
		}
		else
		{
		stk.push(x);
		}
	}
	

	// Potential candidate?
	Celeb = stk.top();
	stk.pop();

	// Check if C is actually
	// a celebrity or not
	for (int i = 0; i < n; i++)
	{
		// In case a person does not
		// know 'C' or 'C' doesn't
		// know any person, return -1
		if ( (i != Celeb) &&
				(knows(Celeb, i) ||
				!knows(i, Celeb)) )
			return -1;
	}

	return Celeb;
}

// Driver code
int main()
{
	int n = 4;
	int id = findTheCelebrity(n);
	id == -1 ? cout << "No celebrity is present" :
			cout << "Celebrity ID " << id;
	return 0;
}

Java Implementation

Below given is the Java implementation of this approach.

Code:

// Java program to find celebrity using
// stack data structure
import java.util.Stack;

class Main
{

	static int MATRIX[][] = { { 0, 0, 0, 1 },
							{ 0, 0, 0, 1 },
							{ 0, 0, 0, 1 },
							{ 0, 0, 0, 0 } };

	// Returns true if x knows
	// y, else false 
	static boolean knows(int x, int y)
	{
		boolean res = (MATRIX[x][y] == 1) ?
									true :
									false;
		return res;
	}

	// Finds the potential celebrity, else returns -1
	static int findTheCelebrity(int n)
	{
		Stack<Integer> stk = new Stack<>();
		int celeb;

		// Step 1 :Push everybody
		// onto stack
		for (int i = 0; i < n; i++)
		{
			stk.push(i);
		}

		while (stk.size() > 1)
		{
			// pop two persons, out of which we 
			// will eliminate the one who is not a 
			// celebrity
			int a = stk.pop();
			int b = stk.pop();

			// Push the one who is our potential celebrity
			// and eliminate the other
			if (knows(a, b))
			{
				stk.push(b);
			}

			else
				stk.push(a);
		}
	
		// if stack becomes empty then there's no celeb
		// so return -1
		if(stk.empty())
			return -1;

		celeb = stk.pop();

		// Check whether the last
		// element of stack is 
		// celebrity or not
		for (int i = 0; i < n; i++)
		{
			// in case celeb knows any person 'i'
			// or 'i' does not knows the celeb
			// then return -1, where i != celeb 
			if (i != celeb && (knows(celeb, i) ||
						!knows(i, celeb)))
				return -1;
		}
		return celeb;
	}

	// Driver Code
	public static void main(String[] args)
	{
		int n = 4;
		int result = findTheCelebrity(n);
		if (result == -1)
		{
			System.out.println("No Celebrity is present");
		}
		else
			System.out.println("Celebrity ID " +
										result);
	}
}

Python Implementation

Below given is the Python implementation of this approach.

Code:

# Python3 program to find celebrity

N = 8

MATRIX = [ [ 0, 0, 0, 1 ],
		[ 0, 0, 0, 1 ],
		[ 0, 0, 0, 1 ],
		[ 0, 0, 0, 0 ] ]

def knows(x, y):
	
	return MATRIX[x][y]

# Finds the potential celebrity, else returns -1
def findTheCelebrity(n):
	
	# Handle trivial
	# case of size = 2
	stk = []

	# Push everybody to stack
	for i in range(n):
		stk.append(i)


	# Find the potential celebrity
	while (len(stk) > 1):
	
		# Pop two elements from stack
		x = stk.pop()
		y = stk.pop()
		
		# if x knows y, then y maybe a celeb, else x maybe a celeb
		if (knows(x, y)):
			stk.append(y)
		else:
			stk.append(x)
			
	# if stack becomes empty then no one is the celeb
	if(len(stk) == 0):
		return -1
		
	# checking for our potential celebrity
	celeb = stk.pop();

	if (knows(celeb, y)):
		celeb = y
		
	if (knows(celeb, x)):
		celeb = x

	# confirm if our potential celebrity celeb is
	# celebrity or not
	for i in range(n):
	
		# in case celeb knows any person 'i'
		# or 'i' does not knows the celeb
		# then return -1, where i != celeb 
		if ((i != celeb) and
		(knows(celeb, i) or
		not(knows(i, celeb)))):
			return -1

	return celeb
	
# Driver code
if __name__ == '__main__':
	
	n = 4
	celeb_id = findTheCelebrity(n)
	
	if celeb_id == -1:
		print("No celebrity is present")
	else:
		print("Celebrity ID ", celeb_id)

Output:

Celebrity ID 3

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 = 00 and j will be n−1n−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−10−>N−1, and confirm whether the index is actually celebrity or not.

C++ Implementation

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

Code:

// C++ program to find celebrity
#include<bits/stdc++.h>
using namespace std;
#define N 4
int findTheCelebrity(int M[N][N], int n)
	{
		// initialize i as starting index
		// and j as ending index
		int i = 0, j = n - 1;
		while (i < j) {
			if (M[j][i] == 1) // then, j knows i
				j--;  //decrement j
			else // j does not knows i so i cannot be the celebrity
				i++;  // increment i
		}
		// i will finally point to our potential celebrity
		int celebIdx = i;

		// finally, confirm whether the last remaining element is
		// actually a celebrity or not
		for (i = 0; i < n; i++) {
			if (i != celebIdx) {
				if (M[i][celebIdx] == 0
					|| M[celebIdx][i] == 1)
					return -1;
			}
		}
		// if the loop doesnt fails and reaches here successfully,
		// then it is our celebrity
		return celebIdx;
	
}


int main()
	{
		int M[N][N] = { { 0, 0, 1, 0 },
					{ 0, 0, 1, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 0, 1, 0 } };

		int idx = findTheCelebrity(M, 4);

		if (idx == -1)
			cout<<("There is no celebrity present!");
		else {
			cout<<
				"The celebrity index is : " << idx;
		}
		return 0;
	}

Java Implementation

Below given is the Java implementation of this approach.

Code:

// Java program to find celebrity
// in the given Matrix of people
// Code by Sparsh_cbs

import java.io.*;

class Main {
	public static void main(String[] args)
	{
		int[][] M = { { 0, 0, 1, 0 },
					{ 0, 0, 1, 0 },
					{ 0, 0, 0, 0 },
					{ 0, 0, 1, 0 } };

		int idx = findTheCelebrity(M, 4);

		if (idx == -1)
			System.out.println("No celebrity found!");
		else {
			System.out.println(
				"The celebrity index is : " + idx);
		}
	}
	public static int findTheCelebrity(int M[][], int n)
	{
		// initialize i as starting index
		// and j as ending index
		int i = 0, j = n - 1;
		while (i < j) {
			if (M[j][i] == 1) // then, j knows i
				j--;
			else // j does not knows i so i cannot be the celebrity
				i++;
		}
		// i will finally point to our potential celebrity
		int celebidx = i;

		// finally, confirm whether the last remaining element is
		// actually a celebrity or not
		for (i = 0; i < n; i++) {
			if (i != celebidx) {
				if (M[i][celebidx] == 0
					|| M[celebidx][i] == 1)
					return -1;
			}
		}
		// if the loop doesnt fails and reaches here successfully,
		// then it is our celebrity
		return celebidx;
	}
}

Python Implementation

Below given is the Python implementation of this approach.

Code:

# Python3 solution
class Solution:

	# Function to determine whether there is celebrity or not.
	# return celebrityindex if celebrity else -1
	def findTheCelebrity(self, M, n):
		# code here
		i = 0
		j = n-1
		celebIdx = -1
		# initialize i as starting index
		# and j as ending index
		while(i < j):
			if M[j][i] == 1:  # if j knows i
				j -= 1
			else:  # j does not knows i so i cannot be the celebrity
				i += 1

		celebIdx = i
		for k in range(n):
			if celebIdx != k:
				if M[celebIdx][k] == 1 or M[k][celebIdx] == 0:
					return -1

		return celebIdx


n = 4
m = [[0, 0, 1, 0],
	[0, 0, 1, 0],
	[0, 0, 0, 0],
	[0, 0, 1, 0]]
ob = Solution()
result = ob.findTheCelebrity(m,n)
print("The Celebrity is present at index = ", result)

Output:

The Celebrity is present at index =  2

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)$.

Conclusion

In this article we learned about the celebrity problem. Let us once go through what we learned till now —

In the celebrity problem, we have to find out the celebrity. A celebrity is one, who is known by everyone but does not knows anyone.
In the brute force approach, we used two loops to solve our problem. But that resulted in quadratic time complexity.
After that, we saw the graph approach where we used the indegree and outdegree arrays to find our celebrity. It was an improvement over the time complexity and resulted in a linear time complexity solution. However, it used some space.
We used the recursion technique where using the information we gained through $N-1$ candidates, we were able to determine whether the 1 person is celeb or not. Here also we used some stack space, but got a linear time complexity.
Using the stack approach was a very good approach for this problem, and by eliminating the candidates who cannot be the celebrity, we were able to find out our actual celebrity.
The best or optimal of all the approaches was the two pointers approach where we were able to solve the problem using two variables one at the start index and another at the end. We could come up with a linear time complexity solution, and no space requirement at all!

FAQ

Q. Can there be two celebrities in the problem?

A. No, because, as the problem already stated that the celebrity should be known by everyone, and it should not know anyone, so there is no chance that two people can be a celebrity, because of the given constraints, they are known to everyone and they cannot know anyone. So, there will be a contradiction if two person become celebrities.

Author

Deepa Pandey

View all posts

The Celebrity Problem

Scope

Takeaways

Problem Statement

Example

Constraints

Approach 1: Brute Force

Implementation in C++, Java and Python

C++ Implementation

Java Implementation

Python Implementation

Time Complexity Analysis

Space Complexity Analysis

Approach 2 – Using Graphs

Implementation in C++, Java and Python

C++ Code

Java Code

Python Code

Time Complexity Analysis

Space Complexity Analysis

Approach 3 – Using Recursion

Finding our potential celebrity :

Algorithm

Implementation in C++, Java & Python

C++ Code

Java Code

Python Code

Time Complexity Analysis

Space Complexity Analysis

Approach 4: Using Stack + Elimination Technique

Implementation in C++, Java and Python

C++ Implementation

Java Implementation

Python Implementation

Time Complexity Analysis

Space Complexity Analysis

Approach 5: Two Pointer approach

Intuition behind the Two Pointers approach

Algorithm :

C++ Implementation

Java Implementation

Python Implementation

Time Complexity Analysis

Space Complexity Analysis

Conclusion

FAQ

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Featured articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?