The Celebrity Problem
In this blog ,we will discuss the following things:
- Analysis of Problem
- Approach 1(Brute Force)
- Approach 2(Stack Solution)
Analysis of Problem
Celebrity problem is one of the most important problem asked in interviews. Let’s understand it’s problem statement first
Given an NxN matrix which represents people at a party such that if element of row i and column j is set to one it means that ith person knows jth person.
A celebrity is a person who is known to all but doesn’t know anyone at the party.
In the above example, although a row is present with all 0’s which means the 2nd person doesn’t know anyone in the party.
But still he is not the celebrity because 3rd person doesn’t know him. So output for above example will be -1.
So,if you go to a party of N people,find if there is a celebrity in the party or not.If a celebrity exists,find him/her ,else return -1.
· It is possible that no celebrity exists among all the people present in the party.
· There can never be more than one celebrity in one party.
Approach 1(Brute Force)
Steps:
- Check for each and every element whether they know each other.
- The element that satisfy all the criteria and doesn’t know any other element is the celebrity.
Code:
int getId(int M[MAX][MAX], int n)
{
int celebrity = -1;
for(int i = 0; i < n; i++)
{
int f = 0;
for(int j = 0; j < n; j++)
{
if(M[i][j] == 1)
{
f = 1;
break;
}
}
if(f == 0) celebrity = i;
}
if(celebrity == -1) return -1;
else
{
int f = 0;
for(int i = 0; i < n; i++)
{
if(i != celebrity && M[i][celebrity] != 1)
{
f = 1;
break;
}
}
if(f == 0) return celebrity;
}
return -1;
}
Analysis of Brute Force Method (The Celebrity problem)
The above code runs two nested loops to search for a celebrity. This will take quadratic time complexity.
Time Complexity : O(n²)
Space Complexity : O(1)
Approach 2(Stack Solution)
Steps:
- Put all indexes(people in the party) into the stack.
- Pop two elements from the top(say A and B) and check whether any one of them knows the other element.
- Push the element back into the stack that doesn’t know the other element(who has the chance to become a celebrity).
- Repeat second and third step till only one element is left in the stack.
- Now, check two conditions for the potential element. If any element doesn’t know the potential element or potential element knows any other element return -1 in both the cases.
- If potential element passes all the cases than it is the celebrity!
Code:
#include <bits/stdc++.h>
using namespace std;
int CelebrityProblem(vector<vector<int>>& v1)
{
stack<int> s1;
for (int i = 0; i<v1.size(); i++)
s1.push(i); //push all the elements into the stack
while (s1.size()>1)
{
int temp1 = s1.top();
s1.pop();
int temp2 = s1.top();
s1.pop();
if (v1[temp1][temp2]) //if temp1 knows temp2
s1.push(temp2); //push temp2
else
s1.push(temp1); //push temp1
}
int potential_celeb=s1.top(); //checking for only one left over element in stack
for(int i=0; i<v1.size(); i++)
{
if(i==s1.top())
continue;
if(v1[potential_celeb][i]==1) //if the potential element knows someother element return -1
return -1;
if(v1[i][potential_celeb]!=1) //if someother element doesn’t know the potential element return -1
return -1;
}
return potential_celeb;
}
int main()
{
vector<vector<int>> v1{ {0,0,1,1},
{1,0,1,0},
{0,1,0,0},
{0,1,1,0} };
int celebrity = CelebrityProblem(v1);
if(celebrity == -1)
cout<<”No Celebrity Exists!”<<endl;
else
cout<<”Celebrity is Person Number “<<celebrity<<endl;
return 0;
}
Analysis of Stack Solution
This efficient solution takes the only loop to find the celebrity element in the problem. So, time complexity will be linear
Time Complexity: O(n)
Space Complexity: O(1)
This problem is based on a 2-D matrix and intuitively we always consider that the 2-D matrix takes O(n²) complexity time to solve a problem.
But there is some 2-D matrix Question which takes O(n) time complexity and this problem is one of them.
Thank you for reading!
