The Celebrity Problem

A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of N people, find if there is a celebrity in the party or not.
A square NxN matrix M[][] 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. Here M[i][i] will always be 0.

Note: Follow 0 based indexing.

• Time : O(n)
• Space : O(1)

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

        return c;
    }
};