Problem Statement

A celebrity is a person who is known by everyone else at the party but does not know anyone in return. Given a square matrix M of size N x N where M[i][j] is 1 if person i knows person j, and 0 otherwise, determine if there is a celebrity at the party. Return the index of the celebrity or -1 if no such person exists.

Note that M[i][i] is always 0.

Examples

Example 1:

Input: M = [ [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0] ]
Output: 1

Explanation: Person 1 does not know anyone and is known by persons 0, 2, and 3. Therefore, person 1 is the celebrity.

Example 2:

Input: M = [ [0, 1], [1, 0] ]
Output: -1

Explanation: Both persons know each other, so there is no celebrity.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A naive approach to solve this problem is to count all the persons that are known for each person and to count all the person that each person knows. This way the celebrity can be identified by finding the person who is known by all other people and who does not know any person.

Approach:

1. Create two lists to count how many people each person knows and how many people know each person.
2. Iterate through the matrix to update the counters based on whether a person knows another person.
3. After populating the counters, iterate through them to find a person who is known by everyone else but does not know anyone. If such a person is found, return their index.
4. If no such person is found, return -1 indicating there is no celebrity.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the index of celebrity
    int celebrity(vector<vector<int>> &M){
        
        // Size of given matrix
        int n = M.size();
        
        /* To store count of people who 
        know person of index i */
        vector<int> knowMe(n, 0);
        
        /* To store count of people who 
        the person of index i knows */
        vector<int> Iknow(n, 0);
        
        // Traverse on given matrix
        for(int i=0; i < n; i++) {
            for(int j=0; j < n; j++) {
                
                // If person i knows person j
                if(M[i][j] == 1) {
                    knowMe[j]++;
                    Iknow[i]++;
                }
            }
        }
        
        // Traverse for all persons to find the celebrity
        for(int i=0; i < n; i++) {
            
            // Return the index of celebrity
            if(knowMe[i] == n-1 && Iknow[i] == 0) {
                return i;  
            }
        }
        
        // Return -1 if no celebrity is found
        return -1;
    }
};

int main() {
    vector<vector<int>> M = {
         {0, 1, 1, 0}, 
         {0, 0, 0, 0}, 
         {1, 1, 0, 0}, 
         {0, 1, 1, 0}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to find the index of celebrity
    int ans = sol.celebrity(M);
    
    cout << "The index of celebrity is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N^2) (where N is the size of square matrix)
  • Traversing the given square matrix to populate the two lists takes O(N^2) time.
  • Traversing on the lists to identify the celebrity takes O(N) time.
• Space Complexity:O(N)
  • The two lists to store the count of how many people each person knows and how many people know each person takes O(N) space each.

2️⃣ Optimal Approach

Intuition:

Since there can be only one celebrity, instead of finding the celebrity, the people that are not celebrity can be determined. If all such people are found, any person left (if it exists) will be the celebrity.

The two conditions to identify the celebrity is:

• The celebrity should be known by every person.
• There should be no person that celebrity knows.

Approach:

1. Set up two pointers, one at the top of the matrix and one at the bottom.
2. Use the pointers to compare individuals:
   1. If the person at the top pointer knows the person at the bottom pointer, move the top pointer down (as it cannot be the celebrity).
   2. If the person at the bottom pointer knows the person at the top pointer, move the bottom pointer up (as it cannot be the celebrity).
   3. If neither knows the other, increment both pointers (as they both cannot be the celebrity).
3. After the traversal, check if the remaining candidate pointed by the top pointer is a valid celebrity by ensuring that everyone knows this person and this person knows no one.
4. If a valid celebrity is found, return the index; otherwise, return -1 indicating there is no celebrity.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the index of celebrity
    int celebrity(vector<vector<int>> &M){
        
        // Size of given matrix
        int n = M.size();
        
        // Top and Down pointers
        int top = 0, down = n-1;
        
        // Traverse for all the people
        while(top < down) {
            
            /* If top knows down, 
            it can not be a celebrity */
            if(M[top][down] == 1) {
                top = top + 1;
            }
            
            /* If down knowns top, 
            it can not be a celebrity */
            else if(M[down][top] == 1) {
                down = down - 1;
            }
            
            /* If both does not know each other, 
            both cannot be the celebrity */
            else {
                top++;
                down--;
            }
        }
        
        // Return -1 if no celebrity is found
        if(top > down) return -1;
        
        /* Check if the person pointed 
        by top is celebrity */
        for(int i=0; i < n; i++) {
            if(i == top) continue;
            
            // Check if it is not a celebrity
            if(M[top][i] == 1 || M[i][top] == 0) {
                return -1;
            }
        }
        
        // Return the index of celebrity
        return top;
    }
};

int main() {
    vector<vector<int>> M = {
         {0, 1, 1, 0}, 
         {0, 0, 0, 0}, 
         {1, 1, 0, 0}, 
         {0, 1, 1, 0}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to find the index of celebrity
    int ans = sol.celebrity(M);
    
    cout << "The index of celebrity is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the size of given square matrix)
  • Eliminating persons takes O(N) time.
  • Checking if the last candidate is a celebrity takes O(N) time.
• Space Complexity:O(1)
  • Using only a couple of variables.