celebrity problem

Find The Celebrity Problem, Party of N People Explained

Problem Statement

The celebrity problem also known as find the celebrity problem, You are in a party of N people, where only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. Your task is to find the stranger (celebrity) at the party.

You will be given a square matrix M[][] where if an element of row i and column j  is set to 1 it means the ith person knows the jth person. You need to complete the function getId() which finds the id of the celebrity if present else returns -1. The function getId() takes two arguments, the square matrix M and its size N.

Here, M[i][i] will be equal to zero.

Note: Expected time complexity is O(N) with constant extra space.

Input:


You are in a party of N people, where only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone in the party. Your task is to find the stranger (celebrity) at the party.

You will be given a square matrix M[][] where if an element of row i and column j  is set to 1 it means the ith person knows jth person. You need to complete the function getId() which finds the id of the celebrity if present else returns -1. The function getId() takes two arguments, the square matrix M and its size test case contains a number denoting the size of the matrix M. Then in the next line are space-separated values of the matrix M.

Output:

For each test, case output will be the id of the celebrity if present (0 based index). Else -1 will be printed.

User Task:
The task is to complete the function getId() which returns the Id of celebrity if present, else -1.

Constraints:
1 <= T <= 50
2 <= N <= 501
0 <= M[][] <= 1

Example:

Input :
2
3
0 1 0 0 0 0 0 1 0
2
0 1 1 0

Output :
1
-1

Analysis of Problem Statement

Problem statement is a bit confusing. So let us understand it more clearly.

There are N people present in a party and there may be a celebrity present among them.

Who is the celebrity ?

The definition of the celebrity according to the problem statement is that he is known to everyone which means every other (N-1) person knows him but the celebrity doesn’t know anyone in the party.

The celebrity may or may not present in the party. If present you have find him and return its Index Number, if not then return -1.

How to find the celebrity ?

According to problem statement, you are given a matrix M[][], let consider it as example,

celebrity problem

The above Matrix will be given and if M[i][j] = 1, it means ith person knows jth person.

For example, in above Matrix, 0th person knows 2nd person.

NOTE only ith person knows jth person, we are still not sure that whether jth person knows ith person or not.

In the above example, 2nd person is the celebrity because, every other person knows him and 2nd person doesn’t know anyone.

OUTPUT will be 2 for the above example.

Let’s take another example,

celebrity problem

In this example, there is no celebrity present in the party, the reason for it is that there is no person present who doesn’t know anyone in the party, at least one person is known to everyone.

So, output for above example will be -1.

Hope Problem Statement is clear to you all.

Naive Method

As you have observed one thing above, that if any row is present with all 0’s, then that person may be the candidate for the Celebrity.

But this is not only the criteria for being a celebrity, you also have to be sure that every other person knows him.

For example,

celebrity problem

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 two criteria needs to be fulfilled for being a Celebrity. Now let see the code for implementing the above logic.

Code for C/C++ ( Naive Method)

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

We have implemented the same thing we discussed above. We searched for a row with all elements as 0. If found, then we made sure that everyone knows that person or not. If yes, we return that candidate or else we returned -1.

Analysis of Naive 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^2)
Space Complexity : O(1)


But the Question asks us that expected time complexity is O(N) with constant extra space.

Can you solve it in linear time ?

It is highly recommended to try it once. The Naive Solution was a cakewalk but the main challenge is to solve it in Linear time.

Efficient Solution (MasterStroke)

The intuition for this solution is that if A knows B, then A cannot be the celebrity and if A doesn’t know B then B cannot be the celebrity.

Yes, it’s as simple as that, it’s obvious intuition. If A knows B, then A knows at least one person in the party which is against the rule of becoming a celebrity.

Similarly, if A doesn’t know B, at least one person is present in the party who doesn’t know B. But the criteria for a celebrity in celebrity problem is that he should be known to everyone. So B violates the rule.

Let us understand it more clearly by an example,

Here we will start from 0th person and 4th person, if 0th person knows 4th person, 0th person cannot be the celebrity so we will move to 1st person.

Similarly, if 0th person doesn’t know 4th person, 4th person cannot be a celebrity, so we will move to 3rd index. It is something like two pointer approach.

Now we will use this intuition to find the candidate in the 2-D matrix.

celebrity problem

For this above matrix, we will start from the M[start][end] position. Here (start = 0) and (end = 4).

If M[start][end] = 1, we are sure that 0th person knows 4th person, so 0th person cannot be the celebrity. So, we will move down or we will increment our start.

We will do this above process, until (start < end).

Let’s see the code for better understanding,

Code in C/C++(Efficient Solution)

int getId(int M[MAX][MAX], int n)
{
    int start = 0; 
    int end = n - 1; 
  
   
    while (start < end) 
    { 
        if (M[start][end] == 1) 
            start++; 
        else
            end--; 
    } 
  
    for (int i = 0; i < n; i++) 
    { 
        if ( (i != start) && (M[start][i] == 1 || M[i][start] == 0)) 
            return -1; 
    } 
  
    return start; 
} 

Let’s understand it more clearly,

Initially start = 0 and end = 4, we checked that if M[0][4] is 1 or 0. In this example it’s 0, so we decrement our last by 1 because 4th person cannot be the celebrity for sure.

celebrity problem

Now, start = 0 and last = 3. Again we check M[0][3], it is again 0, so we decrement last again.

Now, start = 0 and last = 2. Again we check M[0][2], this time it is 1, so we increment start because 0th person knows 2nd person, so obviously 0th person cannot be celebrity this time.

celebrity problem

This way we move till (start < end). Now we may say that M[start] can be a celebrity in problem but still, we have to confirm it as we did in Naive Method.

If confirmation fails, then there is no celebrity present in the party else M[start] is the celebrity.

Hope the idea behind the efficient Solution is clear to you.

Analysis of Efficient 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^2) 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.
Hope you understand to find the Celebrity Problem.

[Dynamic Programming][Greedy algorithms with example]

That’s all folks..!!!

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

Your email address will not be published. Required fields are marked *