**Problem Statement**

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

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

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,

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,

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

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

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)

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

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.

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

**.**

*the Celebrity Problem*[

**][**

*D*ynamic Programming**]**

*Greedy algorithms with example*That’s all folks..!!!