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:**

```
1
```

**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, j
*j*(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 j
*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.

*// 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 *T**r**u**e*, 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
*I**n**d**e**g**r**e**e*and*O**u**t**d**e**g**r**e**e*, 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*T**r**u**e*or not. If it returns a*T**r**u**e*, then increment the*O**u**t**d**e**g**r**e**e*by 11 (because a node is directed from i to j), and also increment the*I**n**d**e**g**r**e**e*by 11. - Run another nested loop to find the element whose
*O**u**t**d**e**g**r**e**e*is 0 and Indegree*I**n**d**e**g**r**e**e*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(*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*th step in the recursion, then we will be comparing the *X*th 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
*k**n**o**w**s*(*a*,*b*) that will tell us whether a knows b or not. So, if the*i**d*returned by the recursive function knows any of the*N*−1 people, then there is no chance that*i**d*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*i**d*to our function. - Finally we will check if
*i**d*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 —
- Suppose, our popped elements are index
*i*and index*j*, where i!=j*i*!=*j*is mandatory - Now, if matrix[i][j]=1
*m**a**t**r**i**x*[*i*][*j*]=1, then that means i know j, so push back*j*into the stack, but not*i*. So,*i*get eliminated. - Otherwise, if matrix[j][i]=1
*m**a**t**r**i**x*[*j*][*i*]=1, then push*i*into the stack and eliminate*j*.

- Suppose, our popped elements are index
- 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−1
*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−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.