The Celebrity Problem

Please upvote if you like it!!!!!!!!!!!!

Problem Statement:- A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of N people, find if there is a celebrity in the party or not. A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j is set to 1 it means ith person knows jth person. Here M[i][i] will always be 0.

• Note: Follow 0 based indexing.
• Follow Up: Can you optimize it to O(N)

Input:

• N = 3
• M[][] = {{0 1 0},
  {0 0 0},
  {0 1 0}}

Output: 1
Explanation: 0th and 2nd person both know 1. Therefore, 1 is the celebrity.

Approach 1: ( Brute force )
Just check each row and column for each index one by one and return accordingly.

~Time Complexity: O(N^2)

Approach 2: ( Optimised using Stack)

1. Take a stack and pull all elements into it.
2. Take a loop iterate until stack having one element and perform below operation.
   • In each iteration take 'A' int variable initialize with top of stack, then pop, Do same for 'B' int variable.
   • Check if 'A' knows 'B', then push 'B' again into stack. else push 'A' again into stack.
3. After previous loop we left with one element in stack and might be that element is our potential celebrity, then verify with below operation
   • Row check all 0's for that celebrity
   • Column check all 1's except diagonal for that celebrity
4. If our potential celebrity is verifed, return that value.

~Time Complexity:- O(N)

C++ Code:-

//Function to find if there is a celebrity in the party or not.
    bool knows(int a, int b,vector<vector<int> >& M){
        if(M[a][b]==1) return true;
        return false;
    }
    int celebrity(vector<vector<int> >& M, int n) 
    {
        // code here 
        stack<int> st;
        for(int i=0;i<n;i++){
            st.push(i);
        }
        while(st.size()>1){
            int a=st.top();
            st.pop();
            int b=st.top();
            st.pop();
            if(knows(a,b,M))// A knows B
                st.push(b);
            else
                st.push(a);
        }
        int Candidate=st.top();
        
        //Row check
        int rowCount=0;
        for(int i=0;i<n;i++){
            if(M[Candidate][i]==0)rowCount++;
        }
        
        if(rowCount != n) return -1;
        
        //Column check
        int colCount=0;
        for(int i=0;i<n;i++){
            if(M[i][Candidate]==1) colCount++;
        }
        
        if(colCount != n-1) return -1;
        
        return Candidate;
    }