Celebrity Problem

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:

Create two lists to count how many people each person knows and how many people know each person.
Iterate through the matrix to update the counters based on whether a person knows another person.
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.
If no such person is found, return -1 indicating there is no celebrity.

Dry Run:

Solution:

#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;
}
import java.util.*;

class Solution {
    // Function to find the index of celebrity
    public int celebrity(int[][] M) {
        
        // Size of given matrix
        int n = M.length;
        
        /* To store count of people who 
        know person of index i */
        int[] knowMe = new int[n];
        
        /* To store count of people who 
        the person of index i knows */
        int[] Iknow = new int[n];
        
        // 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;
    }

    public static void main(String[] args) {
        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 = new Solution(); 
        
        // Function call to find the index of celebrity
        int ans = sol.celebrity(M);
        
        System.out.println("The index of celebrity is: " + ans);
    }
}
class Solution:
    # Function to find the index of celebrity
    def celebrity(self, M):
        
        # Size of given matrix
        n = len(M)
        
        # To store count of people who 
        # know person of index i
        knowMe = [0] * n
        
        # To store count of people who 
        # the person of index i knows
        Iknow = [0] * n
        
        # Traverse on given matrix
        for i in range(n):
            for j in range(n):
                
                # If person i knows person j
                if M[i][j] == 1:
                    knowMe[j] += 1
                    Iknow[i] += 1
        
        # Traverse for all persons to find the celebrity
        for i in range(n):
            
            # Return the index of celebrity
            if knowMe[i] == n - 1 and Iknow[i] == 0:
                return i  
        
        # Return -1 if no celebrity is found
        return -1

if __name__ == "__main__":
    M = [
        [0, 1, 1, 0], 
        [0, 0, 0, 0], 
        [1, 1, 0, 0], 
        [0, 1, 1, 0]
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution() 
    
    # Function call to find the index of celebrity
    ans = sol.celebrity(M)
    
    print("The index of celebrity is:", ans)
class Solution {
    // Function to find the index of celebrity
    celebrity(M) {
        
        // Size of given matrix
        const n = M.length;
        
        /* To store count of people who 
        know person of index i */
        let knowMe = new Array(n).fill(0);
        
        /* To store count of people who 
        the person of index i knows */
        let Iknow = new Array(n).fill(0);
        
        // Traverse on given matrix
        for (let i = 0; i < n; i++) {
            for (let 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 (let 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;
    }
}

const M = [
    [0, 1, 1, 0], 
    [0, 0, 0, 0], 
    [1, 1, 0, 0], 
    [0, 1, 1, 0]
];

/* Creating an instance of 
Solution class */
const sol = new Solution(); 

// Function call to find the index of celebrity
const ans = sol.celebrity(M);

console.log("The index of celebrity is:", ans);

Complexity Analysis:

Time Complexity: O(N²) (where N is the size of square matrix)

Traversing the given square matrix to populate the two lists takes O(N²) 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.

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:

Set up two pointers, one at the top of the matrix and one at the bottom.
Use the pointers to compare individuals:
- 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).
- 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).
- If neither knows the other, increment both pointers (as they both cannot be the celebrity).
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.
If a valid celebrity is found, return the index; otherwise, return -1 indicating there is no celebrity.

Dry Run:

Solution:

#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;
}
import java.util.*;

class Solution {
    // Function to find the index of celebrity
    public int celebrity(int[][] M) {
        
        // Size of given matrix
        int n = M.length;
        
        // 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 knows top, 
            it can not be a celebrity */
            else if (M[down][top] == 1) {
                down = down - 1;
            }
            
            /* If both do 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;
    }

    public static void main(String[] args) {
        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 = new Solution(); 
        
        // Function call to find the index of celebrity
        int ans = sol.celebrity(M);
        
        System.out.println("The index of celebrity is: " + ans);
    }
}
class Solution:
    # Function to find the index of celebrity
    def celebrity(self, M):
        
        # Size of given matrix
        n = len(M)
        
        # Top and Down pointers
        top, down = 0, 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 += 1
            
            # If down knows top,
            # it can not be a celebrity
            elif M[down][top] == 1:
                down -= 1
            
            # If both do not know each other,
            # both cannot be the celebrity
            else:
                top += 1
                down -= 1
        
        # Return -1 if no celebrity is found
        if top > down:
            return -1
        
        # Check if the person pointed
        # by top is celebrity
        for i in range(n):
            if i == top:
                continue
            
            # Check if it is not a celebrity
            if M[top][i] == 1 or M[i][top] == 0:
                return -1
        
        # Return the index of celebrity
        return top

if __name__ == "__main__":
    M = [
        [0, 1, 1, 0], 
        [0, 0, 0, 0], 
        [1, 1, 0, 0], 
        [0, 1, 1, 0]
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution() 
    
    # Function call to find the index of celebrity
    ans = sol.celebrity(M)
    
    print("The index of celebrity is:", ans)
class Solution {
    // Function to find the index of celebrity
    celebrity(M) {
        
        // Size of given matrix
        const n = M.length;
        
        // Top and Down pointers
        let 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 knows top, 
            it can not be a celebrity */
            else if (M[down][top] == 1) {
                down = down - 1;
            }
            
            /* If both do 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 (let 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;
    }
}

const M = [
    [0, 1, 1, 0], 
    [0, 0, 0, 0], 
    [1, 1, 0, 0], 
    [0, 1, 1, 0]
];

/* Creating an instance of 
Solution class */
const sol = new Solution(); 

// Function call to find the index of celebrity
const ans = sol.celebrity(M);

console.log("The index of celebrity is:", ans);

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.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts