Finding the Celebrity: A Dive into the GeeksforGeeks Problem of the Day

The GeeksforGeeks Problem of the Day often presents intriguing challenges, and today's problem is no exception. It revolves around identifying a celebrity at a party, using a matrix representation. Let's break down the solution and explore the nuances of this classic problem.

Problem Statement

Given a matrix mat where mat[i][j] = 1 indicates that person i knows person j, and mat[i][j] = 0 indicates otherwise, the task is to find out if there is a celebrity at the party. A celebrity is defined as a person who is known by everyone else but knows no one at the party.

Key Observations

1. Celebrity Properties:

- A celebrity does not know anyone at the party (`mat[i][j] = 0` for all j).

- Everyone at the party knows the celebrity (`mat[j][i] = 1` for all j).

2. Matrix Representation:

- The matrix mat of size n x n captures the acquaintance relationship between the n people at the party.

- If a person i knows person j, then mat[i][j] will be 1.

Solution Approach

The solution involves two primary steps:

1. Tracking Relationships:

- We use two arrays, knowme and iknow, to track how many people know a person and how many people a person knows, respectively.

- We iterate through the matrix and populate these arrays. Specifically, if mat[i][j] = 1, we increment knowme[j] and iknow[i].

2. Identifying the Celebrity:

- After populating the knowme and iknow arrays, we look for a person who is known by everyone else (`knowme[i] == n - 1`) and knows no one (`iknow[i] == 0`).

- If such a person exists, we return their index. Otherwise, we return -1, indicating there is no celebrity.

Code Implementation

Here's the implementation of the solution:

class Solution {
  public:
    // Function to find if there is a celebrity in the party or not.
    int celebrity(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<int> knowme(n, 0), iknow(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    knowme[j]++;
                    iknow[i]++;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (knowme[i] == n - 1 && iknow[i] == 0) {
                return i;
            }
        }
        return -1;
    }
};        

Analysis

The solution efficiently determines the presence of a celebrity with a time complexity of O(n^2), where n is the number of people at the party. This complexity arises from the nested loops used to fill the knowme and iknow arrays. The final check for the celebrity is O(n), making it a straightforward and clear approach.

Conclusion

This problem elegantly demonstrates the use of matrix operations to solve a real-world scenario. The approach highlights the importance of understanding the relationships between elements and efficiently tracking necessary information. It's a great example of how fundamental concepts like arrays and matrices can be applied to solve complex problems.

For those interested in diving deeper, consider exploring variations of this problem, such as finding multiple celebrities or optimizing the solution to reduce the number of comparisons. Happy coding!