Celebrity Problem - Naukri Code 360

Q: How do you solve celebrity problems?

There are various ways through which you can solve celebrity problems. You can solve by brute force approach, recursion, two pointer approach, or by using stack.

Q: What is the time complexity of the celebrity problem?

Time complexity of the celebrity problem depends on the approach of how you solve the problem. The time complexity for celebrity problem is O(N*N).

Introduction

Welcome Back, Ninja! Today this article will discuss one of the most frequently asked questions in Google, Apple, Amazon - “The Celebrity Problem”. Let's start with the problem statement and work our way to the solution.

Problem Statement

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N- 1’ (both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party. Your task is to find out the celebrity at the party. Print the id of the celebrity. If there is no celebrity at the party, then print -1.

Input:

MATRIX = { {0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 0, 0},

{0, 0, 1, 0} }

Output:id = 2

Explanation: The person with ID 2 does not know anyone, but everyone knows him

Note: Given a helper function ‘knows(A, B)’, It will return "true" if the person having id ‘A’ knows the person having id ‘B’ in the party, "false" otherwise. The complexity is determined by the number of calls made to knows (A, B). Hence, You should keep the number of calls to the function ‘knows(A, B)' as low as possible.

Without further ado, let's get started on solutions to this problem.

Approach 1: Brute Force

The first thought that comes to anyone's mind is to see if there is any id that does not know anyone. If such an id exists, it may be a potential candidate for celebrity, but we must first determine whether or not everyone knows it.

The algorithm is as follows:

Initialize an integer variable 'CELEBRITY' := -1.
Run a loop where ‘i’ ranges from 0 to ‘N’ - 1, and check whether the person having id ‘i’ is a celebrity or not. This can be done as follow -:
- Initialise two boolean variables, ‘KNOWANY’ and ‘KNOWNTOALL’.
- Run a loop where ‘j’ ranges from 0 to ‘N’ - 1. If ‘knows(i, j)’ returns false for all ‘j’, then set ‘KNOWANY’:= false
- Run a loop where ‘j’ ranges from 0 to ‘N’ - 1 and if ‘knows(j, i)’ return true for all ‘j’ except when ‘j’ = ‘i’, then set ‘KNOWNTOALL’:= true
- If ‘KNOWANY’ is ‘false’ and ‘KNOWNTOALL’ is ‘true’, then assign ‘CELEBRITY’:= ‘i’ and break the loop.
Return ‘CELEBRITY’.
To fully comprehend the above approach, the C++ code is provided below.

Implementation in C++, Java and Python

C++ Code

C++ Code

/*
    Time complexity: O(N*N)
    Space complexity: O(1)
    
    Where 'N' is the number of people at the party.
*/

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

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

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]; 
    
}

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++) {
        bool knowAny = false, knownToAll = true;

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

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

        if(!knowAny && knownToAll) {
            celebrity = i;
            break;
        }
    }

    return celebrity;
}

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

You can also try this code with Online C++ Compiler

Run Code

Output:

Python Code

Python Code

def knows(i, j):
    matrix = [
        [0, 0, 1, 0],
        [0, 0, 1, 0],
        [0, 0, 0, 0],
        [0, 0, 1, 0]
    ]
    return matrix[i][j] == 1

def findCelebrity(n):
    for i in range(n):
        is_celebrity = True
        for j in range(n):
            if i != j and (knows(i, j) or not knows(j, i)):
                is_celebrity = False
                break
        if is_celebrity:
            return i
    return -1  

n = 4
celebrity = findCelebrity(n)

if celebrity != -1:
    print(f"{celebrity}")
else:
    print("No celebrity")

You can also try this code with Online Python Compiler

Run Code

Output

Java Code

Java Code

import java.util.*;

public class Main{

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

    static boolean knows(int i, int j) {
        return matrix[i][j] == 1;
    }

    static int findCelebrity(int n) {
        for (int i = 0; i < n; i++) {
            boolean isCelebrity = true;
            for (int j = 0; j < n; j++) {
                if (i != j && (knows(i, j) || !knows(j, i))) {
                    isCelebrity = false;
                    break;
                }
            }
            if (isCelebrity) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int n = 4;
        int id = findCelebrity(n);

        if (id!= -1) {
            System.out.println("Celebrity ID " + id);
        } else {
            System.out.println("No celebrity");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

O(N*N), where ‘N’ is the number of people at the party.

The outer loop will run ‘N’ times and two inner loops both will run ‘N’ times but note they are not nested so overall complexity will be O(N*(N+N))= O(2N*N) = O(N*N)

Space Complexity

O(1). No extra space is used here.

Approach 2: Using Graph

This problem can be modelled as a graph problem. Consider a directed graph having ‘N’ nodes numbered from 0 to ‘N’ - 1. If the helper function ‘knows(i, j)’ returns true, then it means that there is a directed edge from node ‘i’ to node ‘j’. We can observe that if the celebrity is present, it is represented by a global sink i.e node that has indegree n-1 and outdegree 0.

Make two integer arrays, ‘INDEGREE’ and ‘OUTDEGREE’ of size ‘N’. And fill both of them by 0. These arrays will represent the indegree and outdegree of each node.
Run a nested loop where the outer loop ‘i’ ranges from 0 to ‘N’ - 1 and the inner loop ‘j’ ranges from 0 to ‘N’ - 1, and for each pair (i, j) if ‘knows(i, j)’ return true, then increment ‘OUTDEGREE[i]’ by 1 and ‘INDEGREE[j]’ by 1.
Initialize an integer variable ‘CELEBRITY' = -1.
Run a loop where ‘i’ ranges from 0 to ‘N’ - 1, and find ‘i’ for which ‘INDEGREE[i]’ is ‘N’ - 1 and ‘OUTDEGREE[i]’ is 0 if such ‘i’ exist then assign ‘CELEBRITY’:= ‘i’, otherwise keep the value of ‘CELEBRITY’ as -1.
Return ‘CELEBRITY’.

To fully comprehend the above approach, the C++ code is provided below.

Implementation in C++, Java and Python

C++ Code

C++ Code

/*
    Time complexity: O(N*N)
    Space complexity: O(N)

    Where 'N' is the number of people at the party.
*/
#include <bits/stdc++.h>
#include <list>
using namespace std;
  
// Max # of persons in the party
#define N 4
  
//Matrix 
bool MATRIX[N][N] = {{0, 0, 1, 0},{0, 0, 1, 0},{0, 0, 0, 0},{0, 0, 1, 0}};

//Returns True if A knows B else return False 
bool knows(int A, int B)
{
    return MATRIX[A][B];
}

int findCelebrity(int n) {

    // Calculating indegree and outdegree of each nodes.
    vector<int> indegree(n), outdegree(n);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(knows(i, j)) {
                indegree[j]++;
                outdegree[i]++;
            }
        }
    }

    // Finding Celebrity.
    int celebrity = -1;

    for(int i = 0; i < n; i++) {
        if(indegree[i] == n - 1 && outdegree[i] == 0) {
            celebrity = i;
            break;
        }
    }

    return celebrity;
}

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

You can also try this code with Online C++ Compiler

Run Code

Output:

Java Code

Java Code

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

	
	
	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]; }


	static int find_celebrity(int n)
	{

		
		int[] indegree = new int[n];
		int[] outdegree = new int[n];

	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int x = knows(i, j);

				
				outdegree[i] += x;
				indegree[j] += x;
			}
		}

		
		for (int i = 0; i < n; i++)
			if (indegree[i] == n - 1 && outdegree[i] == 0)
				return i;

		return -1;
	}

	
	public static void main(String[] args)
	{
		int n = 4;
		int id = find_celebrity(n);
		if (id == -1)
			System.out.print("No celebrity");
		else
			System.out.print("Celebrity ID " + id);
	}
}

You can also try this code with Online Java Compiler

Run Code

Output

Python Code

Python Code

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


def knows(A, B):

	return MATRIX[A][B]


def FindCelebrity(n):



	
	indegree = [0 for x in range(n)]
	outdegree = [0 for x in range(n)]

	
	for i in range(n):
		for j in range(n):
			x = knows(i, j)

		
			outdegree[i] += x
			indegree[j] += x


	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_ = FindCelebrity(n)

	if id_ == -1:
		print("No celebrity")
	else:
		print("Celebrity ID", id_)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

O(N*N), where ‘N’ is the number of people at the party.

Reason: Because the nested loop will take the time of the order of N*N.

Space Complexity

O(N), where ‘N’ is the number of people at the party.

Reason: The size of the array ‘INDEGREE’ and ‘OUTDEGREE’ will be of the order of ‘N’.

Approach 3: Using Recursion

Is it possible to find the solution to n if the ‘potential celebrity' of n-1 persons is known?

After eliminating n-1 people, a potential celebrity is the only one remaining.

The following approach is used to eliminate n-1 people:

A cannot be a celebrity if A knows B, although B may be.

Else B cannot be a celebrity if B knows A. However, A might be the celebrity.

The intuition described above employs Recursion to find a potential celebrity among n people, recursively calling n-1 people until the base case of 0 people is reached. When there are no people, the value -1 is returned, indicating that there are no potential celebrities.

The ith person and (i-1)th person are compared in the ith stage of recursion to see if one of them knows the other. The potential celebrity is then returned to the (i+1)th stage using the logic outlined above.

When the recursive function has finished its loop, it will return an id. We check to see if this id is unknown to anyone else, but everyone knows it. If this is correct, this ID will be the celebrity.

An algorithm is as follows:

Make a recursive function that takes an integer n as input.
Check the base case; if n is 0, return -1.
Invoke the recursive function to extract the ID of the potential celebrity from the first n-1 elements.
If the id is -1, then n is the potential celebrity and the value is returned.
Return n-1 if the potential celebrity of the first n-1 elements knows n-1 (0 based indexing)
If the celebrity of the first n-1 elements does not know n-1, return the celebrity of the n-1 elements' id (0 based indexing)
Otherwise, return -1.

Create a function and determine whether the id returned by the function is surely that of the celebrity.

To fully comprehend the above approach, the C++ code is provided below.

Implementation in C++, Java and Python

C++ Code

C++ Code

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

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

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]; 
    
}

// Returns -1 if a 'potential celebrity'
// is not present. If present,
// returns id (value from 0 to n-1).
int findCelebrity(int n)
{
// base case - when n reaches 0 , returns -1
// since n represents the number of people,
// 0 people implies no celebrity(= -1)
if (n == 0)
return -1;

// find the celebrity with n-1
// persons
int id = findCelebrity(n - 1);

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

// if the id knows the nth person
// then the id cannot be a celebrity, but nth person
// could be one
else if (knows(id, n - 1)) {
return n - 1;
}
// if the nth person knows the id,
// then the nth person cannot be a celebrity and the id
// could be one
else if (knows(n - 1, id)) {
return id;
}

// if there is no celebrity
return -1;
}

// Returns -1 if celebrity
// is not present. If present,
// returns id (value from 0 to n-1).
// a wrapper over findCelebrity
int Celebrity(int n)
{
// find the celebrity
int id = findCelebrity(n);

// check if the celebrity found
// is really the celebrity
if (id == -1)
return id;
else {
int c1 = 0, c2 = 0;

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

// if the person is known to
// everyone.
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" : cout << "Celebrity ID " << id;
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Java Code

Java Code


import java.util.*;
public class Main {
    

public 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]; 
    
}

static int findCelebrity(int n)
{

if (n == 0)
return -1;

int id = findCelebrity(n - 1);


if (id == -1)
return n - 1;


else if (knows(id, n - 1) == 1) {
return n - 1;
}

else if (knows(n - 1, id) == 1) {
return id;
}


return -1;
}


int Celebrity(int n)
{
// find the celebrity
int id = findCelebrity(n);


if (id == -1)
return id;
else {
int c1 = 0, c2 = 0;


for (int i = 0; i < n; i++)
if (i != id) {
c1 += knows(id, i);
c2 += knows(i, id);
}

if (c1 == 0 && c2 == n - 1)
return id;

return -1;
}
}


 public static void main(String[] args) 
{
int n = 4;
int id = findCelebrity(n);
if (id == -1)
			System.out.print("No celebrity");
		else
			System.out.print("Celebrity ID " + id);


}
}

You can also try this code with Online Java Compiler

Run Code

Output

Python Code

Python Code


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


def knows(A, B):

	return MATRIX[A][B]


def find_Celebrity(n):


	if (n == 0):
		return 0

	index = find_Celebrity(n - 1)

	if (index == -1):
		return n - 1
	
	elif knows(index, n - 1):
		return n - 1
	
	elif knows(n - 1, index):
		return index
	return - 1


def Celebrity(n):


	index = find_Celebrity(n)

	
	if (index == -1):
		return index
	else:
		c1 = 0
		c2 = 0

		
		for i in range(n):
			if (i != index):
				c1 += knows(index, i)
				c2 += knows(i, index)

		
		if (c1 == 0 and c2 == n - 1):
			return index

		return -1

if __name__ == '__main__':

	n = 4
	index = Celebrity(n)

	if index == -1:
		print("No celebrity")
	else:
		print("Celebrity ID", index)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity: O(n).
The recursive function is called n times, so the time complexity is O(n).

Space Complexity: O(1). As no extra space is required.

Approach 4: Using Stack

If for any pair (i, j) such that ‘i’!= ‘j’, if ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly, if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’. We can use this observation to solve this problem.

The algorithm is as follows:

Create a stack and push all ids in it.
Run a loop while there are more than one element in the stack and in each iteration do the following-:
- Pop two elements from the stack. Let these elements be ‘id1’ and ‘id2’.
- If the person with ‘id1’ knows the person with ‘id2,’ i.e. ‘knows(id1, id2)’ return true, then the person with ‘id1’ cannot be a celebrity, so push ‘id2’ in the stack.
- Otherwise, if the person with ‘id1’ doesn't know the person with ‘id2,’ i.e. knows(id1, id2) return false, then the person with ‘id2’ cannot be a celebrity, so push ‘id1’ in the stack.
Only one id remains in the stack; you need to check whether the person having this id is a celebrity or not, this can be done by running two loops. One checks whether this person is known to everyone or not, and another loop will check whether this person knows anyone or not.
If this person is a celebrity, return his id; otherwise, return -1.

The C++ code for the above approach is provided below to help you fully understand it.

Implementation in C++, Java and Python

C++ Code

C++ Code

/*
    Time complexity: O(N)
    Space complexity: O(N)
    
    Where 'N' is the number of people at the party.
*/

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

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

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]; 
    
}

int findCelebrity(int n) {

    // Create a stack and push all ids in it.
    stack<int> ids;
    for(int i = 0; i < n; i++) {
        ids.push(i);
    }

    // Finding celebrity.
    while(ids.size() > 1) {
        int id1 = ids.top();
        ids.pop();
        int id2 = ids.top();
        ids.pop();
        
        if(knows(id1, id2)) {
            // Because person with id1 can not be celebrity. 
            ids.push(id2); 
        }
        else {
            // Because person with id2 can not be celebrity.
            ids.push(id1); 
        }
    }

    int celebrity = ids.top();
    bool knowAny = false, knownToAll = true;

    // Verify whether the celebrity knows any other person.
    for(int i = 0; i < n; i++) {
        if(knows(celebrity, i)) {
            knowAny = true;
            break;
        }
    }

    // Verify whether the celebrity is known to all the other person.
    for(int i = 0; i < n; i++) {
        if(i != celebrity and !knows(i, celebrity)) {
            knownToAll = false;
            break;
        }
    }

    if(knowAny or !knownToAll) {
        // If verificatin failed, then it means there is no celebrity at 
the party.
        celebrity = -1;
    }

    return celebrity;
}

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

You can also try this code with Online C++ Compiler

Run Code

Output:

Java Code

Java Code

import java.util.*;
import java.util.Stack;

public class Main{
    
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]; 
    
}

static int findCelebrity(int n) {

    
    Stack<Integer> ids = new Stack<>();
    for(int i = 0; i < n; i++) {
        ids.push(i);
    }

    
    while(ids.size() > 1) {
        int id1 = ids.peek();
        ids.pop();
        int id2 = ids.peek();
        ids.pop();
        
        if(knows(id1, id2) == 1) {
             
            ids.push(id2); 
        }
        else {
            
            ids.push(id1); 
        }
    }

    int celebrity = ids.peek();
    boolean knowAny = false, knownToAll = true;

    
    for(int i = 0; i < n; i++) {
        if(knows(celebrity, i) == 1) {
            knowAny = true;
            break;
        }
    }

    
    for(int i = 0; i < n; i++) {
        if(i != celebrity && knows(i, celebrity) == -1 ) {
            knownToAll = false;
            break;
        }
    }

    if(knowAny || !knownToAll) {
    
        celebrity = -1;
    }

    return celebrity;
}


public static void main(String[] args) {

int n = 4;
int id = findCelebrity(n);
if (id == -1)
			System.out.print("No celebrity");
		else
			System.out.print("Celebrity ID " + id);
}
}

You can also try this code with Online Java Compiler

Run Code

Output

Python Code

Python Code


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


def knows(A, B):

	return MATRIX[A][B]

def find_Celebrity(n):

	
	stack = []

	
	for i in range(n):
		stack.append(i)

	
	while (len(stack) > 1):

		
		a = stack.pop()
		b = stack.pop()

	
		if (knows(a, b)):
			stack.append(b)
		else:
			stack.append(a)


	if(len(stack) == 0):
		return -1

	
	c = stack.pop()

	
	if (knows(c, b)):
		c = b

	if (knows(c, a)):
		c = a

	
	for i in range(n):

		
		if ((i != c) and
			(knows(c, i) or
				not(knows(i, c)))):
			return -1

	return c


if __name__ == '__main__':

	n = 4
	id_ = find_Celebrity(n)

	if id_ == -1:
		print("No celebrity")
	else:
		print("Celebrity ID ", id_)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

O(N), where ‘N’ is the number of people at the party.

The number of push and pop operations performed on the stack will be of order ‘N’.

Space Complexity

O(N), where ‘N’ is the number of people at the party. The size of the stack will be of the order of ‘N’.

Approach 5: Two Pointers Approach

If for any pair ('i', ‘j’) such that 'i' != ‘j’, If ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly, if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’.

So, the Two Pointer approach can be used where two pointers can be assigned, one at the start and the other at the end of the elements to be checked, and the search space can be reduced. This approach can be implemented as follow -:

Initialize two integer variables ‘P’:= 0 and ‘Q’:= 'N' - 1. ‘P’ and ‘Q’ will be two pointers pointing at the start and end of search space respectively.
Run a while loop till 'P' < ‘Q’, and in each iteration, do the following.
- If ‘knows(P, Q)’ returns true, then increment ‘P’ by 1.
- If ‘knows(P, Q)’ returns false, then decrement ‘Q’ by 1.
Check whether the person having id ‘P’ is a celebrity or not, this can be done by running two loops. One checks whether this person is known to everyone or not, and another loop will check whether this person knows anyone or not.
If a person with id ‘P’ is a celebrity, return ‘P’. Otherwise, return -1.

The C++ code is provided below to help you fully understand the above approach.

Implementation in C++, Java and Python

C++ Code

C++ Code

/*
    Time complexity: O(N)
    Space complexity: O(1)
    
    Where 'N' is the number of people at the party.
*/

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

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

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]; 
    
}

int findCelebrity(int n) {
    
    // Two pointers pointing at start and end of search space.
    int p = 0, q = n-1; 

    // Finding celebrity.
    while(p < q) {
        if(knows(p, q)) {
            // This means p cannot be celebrity.
            p++;  
        }
        else {
            // This means q cannot be celebrity.
            q--; 
        }
    }

    int celebrity = p;
    bool knowAny = false, knownToAll = true;

    // Verify whether the celebrity knows any other person.
    for(int i = 0; i < n; i++) {
        if(knows(celebrity, i)) {
            knowAny = true;
            break;
        }
    }

    // Verify whether the celebrity is known to all the other person.
    for(int i = 0; i < n; i++) {
        if(i != celebrity and !knows(i, celebrity)) {
            knownToAll = false;
            break;
        }
    }

    if(knowAny or !knownToAll) {
        // If verificatin failed, then it means there is no celebrity at the party.
        celebrity = -1;
    }

    return celebrity;
}

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

You can also try this code with Online C++ Compiler

Run Code

Output:

Java Code

Java Code


import java.util.*;

public class Main {
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]; 
    
}

static int findCelebrity(int n) {
    
   
    int p = 0, q = n-1; 

    
    while(p < q) {
        if(knows(p, q) == 1) {
            
            p++;  
        }
        else {
            
            q--; 
        }
    }

    int celebrity = p;
    boolean knowAny = false, knownToAll = true;

    
    for(int i = 0; i < n; i++) {
        if(knows(celebrity, i) == 1) {
            knowAny = true;
            break;
        }
    }

   
    for(int i = 0; i < n; i++) {
        if(i != celebrity && knows(i, celebrity) == -1) {
            knownToAll = false;
            break;
        }
    }

    if(knowAny || !knownToAll) {
       
        celebrity = -1;
    }

    return celebrity;
}

public static void main(String[] args) {

int n = 4;
int id = findCelebrity(n);
if (id == -1)
			System.out.print("No celebrity");
		else
			System.out.print("Celebrity ID " + id);
}
}

You can also try this code with Online Java Compiler

Run Code

Output

Python Code

Python Code

class CodingNinjas:

	
	def celebrity(self, A, n):
		# code here
		i = 0
		j = n-1
		candidate = -1
		while(i < j):
			if A[j][i] == 1:
				j -= 1
			else:
				i += 1

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

		return candidate


n = 4
matrix = [[0, 0, 1, 0],
	[0, 0, 1, 0],
	[0, 0, 0, 0],
	[0, 0, 1, 0]]
index = CodingNinjas()
ans = index.celebrity(matrix, n)
if ans == -1:
	print("No Celebrity")
else:
	print("Celebrity ID", ans)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

O(N), where ‘N’ is the number of people at the party.

The number of queries from the matrix ‘M’ will be of order ‘N’.

Space Complexity

O(1). No extra space is used here.

If you've made it this far, congratulations Champ. You can now solve "The Celebrity Problem" using five different approaches. Without further ado, let's submit it to Coding Ninjas Studio and get accepted right away.

Frequently Asked Questions

How do you solve celebrity problems?

There are various ways through which you can solve celebrity problems. You can solve by brute force approach, recursion, two pointer approach, or by using stack.

What is the celebrity problem statement?

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N- 1’. A celebrity is a person who is known to everyone but does not know anyone at the party. Your task is to find out the celebrity at the party. Print the ID of the celebrity.

What is the time complexity of the celebrity problem?

The time complexity of the celebrity problem depends on the approach of how you solve the problem. The time complexity for the celebrity problem is O(N*N).

Conclusion

This article addressed one of the most frequently asked questions in Google, Apple, and Amazon: "The Celebrity Problem." There are five approaches for solving "The Celebrity Problem," which are Brute Force, Graph, Recursion, Stack, and the most efficient Two Pointers Approach. We have also provided the intuition, algorithms, and C++ code for each approach to fully comprehend the problem.

It is rigorous practising which helps us to hone our skills. You can find a wide variety of practice problems, specifically for technical interviews, to help you apply your knowledge and ace your interviews.

Apart from this, you can use Coding Ninjas Studio to practice a wide range of DSA questions typically asked in interviews at big MNCs. This will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based organisations.