The Celebrity Problem

A celebrity is a person who is known to all but does not know anyone at a party. A party is being organized by some people.  A square matrix mat 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. You need to return the index of the celebrity in the party, if the celebrity does not exist, return -1.

Note: Follow 0-based indexing.

Examples:

Input: mat[][] = [[0 1 0],
                [0 0 0], 
                [0 1 0]]
Output: 1
Explanation: 0th and 2nd person both know 1. Therefore, 1 is the celebrity. 

Input: mat[][] = [[0 1],
                [1 0]]
Output: -1
Explanation: The two people at the party both know each other. None of them is a celebrity.

Expected Time Complexity: O(n²)
Expected Auxiliary Space: O(1)

Constraints:
1 <= mat.size()<= 3000
0 <= mat[i][j]<= 1

Approach 01:

class Solution {
public:
    // Function to find if there is a celebrity in the party or not.
    int celebrity(vector<vector<int>>& acquaintanceMatrix) {
        int candidate = 0; // Initial candidate for the celebrity
        int numPeople = acquaintanceMatrix.size(); // Number of people at the party

        // Find the potential celebrity
        for (int person = 1; person < numPeople; ++person) {
            // If the current candidate knows this person, then this person becomes the new candidate
            if (acquaintanceMatrix[candidate][person] == 1) {
                candidate = person;
            }
        }

        // Verify if the candidate is actually a celebrity
        for (int person = 0; person < numPeople; ++person) {
            // The candidate should not know anyone else and everyone should know the candidate
            if (person != candidate && 
                (acquaintanceMatrix[candidate][person] == 1 || acquaintanceMatrix[person][candidate] == 0)) {
                return -1; // The candidate is not a celebrity
            }
        }

        return candidate; // Return the candidate as the celebrity
    }
};

from typing import List

class Solution:
    # Function to find if there is a celebrity in the party or not.
    def celebrity(self, acquaintanceMatrix: List[List[int]]) -> int:
        candidate = 0  # Initial candidate for the celebrity
        numPeople = len(acquaintanceMatrix)  # Number of people at the party

        # Find the potential celebrity
        for person in range(1, numPeople):
            # If the current candidate knows this person, then this person becomes the new candidate
            if acquaintanceMatrix[candidate][person] == 1:
                candidate = person

        # Verify if the candidate is actually a celebrity
        for person in range(numPeople):
            # The candidate should not know anyone else and everyone should know the candidate
            if person != candidate and \
               (acquaintanceMatrix[candidate][person] == 1 or acquaintanceMatrix[person][candidate] == 0):
                return -1  # The candidate is not a celebrity

        return candidate  # Return the candidate as the celebrity

Time Complexity

• Finding the Potential Celebrity:

  The first loop iterates through each person once to find the potential celebrity. This takes \( O(n) \) time, where \( n \) is the number of people at the party.

• Verifying the Celebrity:

  The second loop checks the potential celebrity against all other people, which also takes \( O(n) \) time.

• Overall Time Complexity:

  Combining both loops, the overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of additional space for variables such as candidate and numPeople. Therefore, the auxiliary space complexity is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).