03(Aug) The Celebrity Problem

03. The Celebrity Problem

The problem can be found at the following link: Question Link

Problem Description

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 the ith person knows the jth person. You need to return the index of the celebrity at the party; if the celebrity does not exist, return -1.

Note: Follow 0-based indexing.

Example:

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.

My Approach

1. Finding the Potential Celebrity:

• Initialize the potential_celebrity to 0.

• Iterate through the matrix. If mat[potential_celebrity][i] is 1, it means the current potential_celebrity knows i, so update potential_celebrity to i.

1. Validating the Potential Celebrity:

• Iterate through the matrix again to confirm that the potential_celebrity doesn't know anyone and everyone knows the potential_celebrity.

• If any person doesn't know the potential_celebrity or the potential_celebrity knows someone, return -1.

1. Return:

• Return the potential_celebrity if they are confirmed as the celebrity; otherwise, return -1.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), as we iterate through the matrix to find and confirm the celebrity.

• Expected Auxiliary Space Complexity: O(1), as we use a constant amount of additional space.

Code (C++)

class Solution {
public:
    int celebrity(vector<vector<int>>& mat) {
        int n = mat.size();
        int potential_celebrity = 0;
        for (int i = 1; i < n; ++i) {
            if (mat[potential_celebrity][i] == 1) {
                potential_celebrity = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i != potential_celebrity && (mat[potential_celebrity][i] == 1 || mat[i][potential_celebrity] == 0)) {
                return -1;
            }
        }
        return potential_celebrity;
    }
};

Code (Java)

class Solution {
    public int celebrity(int[][] mat) {
        int n = mat.length;
        int potentialCelebrity = 0;
        for (int i = 1; i < n; ++i) {
            if (mat[potentialCelebrity][i] == 1) {
                potentialCelebrity = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i != potentialCelebrity && (mat[potentialCelebrity][i] == 1 || mat[i][potentialCelebrity] == 0)) {
                return -1;
            }
        }
        return potentialCelebrity;
    }
}

Code (Python)

class Solution:
    def celebrity(self, mat):
        n = len(mat)
        a = 0
        b = n - 1

        while a < b:
            if mat[a][b] == 1:
                a += 1
            else:
                b -= 1

        for i in range(n):
            if i != a and (mat[a][i] == 1 or mat[i][a] == 0):
                return -1

        return a

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count