Find the Celebrity

Description:

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 -- celebrity is a person who is known to everyone in a party, but he does not know 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 ii and column j is set to true, then the i^th person knows the j^th person. Please note that, here the M[i][i] will always be zero.

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] = true, else it is equal to false.

Task: Your task is to find out about 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[][] = {{false true false}, 
         {false false false}, 
         {false true false}
        } 
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], M[0][1]=M[2][1].

Example 2:

Input:
N = 2
M[][] ={{false true},
        {true false}
       }
Output:: -1

Explanation: Both of the person know each other in the party, so there is no celebrity in the party.

Solution:

Ok ok, honestly I got this problem on the interview. And I solved it only with a brute-force solution.

Let’s discuss it.

My main idea is to iterate over the array, and check does this person know anybody and does this person knows by other persons. And obviously if so it is a celebrity.

For it we need iterate over array

for (int i = 0; i < n; i++) 

and add 2 variables

 boolean knowsAnyone = false;
 boolean everyoneKnows = true;

then we iterate over a row and check that this person knows anyone

for (int j = 0; j < n; j++) {
   if (matrix[i][j]) {
      knowsAnyone = true;
      break;
   }
}

In the next step, we should check that this person is known by anyone else

for (int j = 0; j < n; j++) {
   if (i != j && !matrix[j][i]) {
      everyoneKnows = false;
      break;
   }
}

And finally, if a person doesn’t know anyone and is known by others that is mean that we found a celebrity.

Time Complexity for this solution is O(N*N), where N is the number of people at the party.

Space Complexity for this solution is constant because we are not using any additional data structures.

And interviewer wanted another solution without adding some hits. I was disappointed and didn’t improve my idea. Unfortunately, I didn’t pass the interview. But I found an elegant idea.

This idea calls Elimination Technique.

The main idea is to eliminate elements step by step.

In the first step, we should put all people into a Stack.

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < n; i++) {
   stack.push(i);
}

Then we should iterate over the stack and get pairs

while (stack.size() > 1) {
   int first = stack.pop();
   int second = stack.pop();
}

When we have a pair we can check does the first person knows the second one

if (matrix[first][second]) {}

And if the first knows the second, that means that the first cannot be the celebrity. Because the celebrity doesn’t know anybody. But the second one still can be a celebrity

if (matrix[first][second]) {
   stack.push(second);
} else{
   stack.push(first);
}

When we have zero elements in the stack → it means we do not have a celebrity.

if (stack.empty()){
   return -1;
}

Also if we have 1 element in the stack we should additionally check that everybody knows it and celebrity doesn’t know anyone

for (int i = 0; i < n; i++) {
   if (i != celeb && (matrix[celeb][i] || !matrix[i][celeb])){
      return -1;
   }
}

And and, that is it. It is so wise. I was shocked. Hope you enjoyed this idea.

Link to resource: https://www.scaler.com/topics/celebrity-problem/