Two Pointers: Celebrity Problem

Problem Statement:

You are given 2D matrix, where in arr[i][j] is 1 if person i knows person j. Else it will be 0.

You need to find the celebrity. A celebrity is a person who is known by everyone at the party but he does not know anyone in return

Example:

Input:

M = [ 
		[0, 1, 1, 0], 
		[0, 0, 0, 0], 
		[1, 1, 0, 0], 
		[0, 1, 1, 0] ]


Output: 1

Explanation:

Person 1 does not know any one, but he is known by everyone.

Solution Explanation: Bruteforce Approach

Take 2 array to keep track of how may people each person knows and how many people know each person.

Iterate through out the matrix by updating the counters based on the person knows another person.

Then iterate both arrays to check if a person is known by everyone but he do not know anyone.

Time Complexity: O(n*n)
Space Complexity: O(n)

Solution Explanation: Two Pointer Approach

In this approach, take a pointer from top left and one from bottom right of the matrix.

If the person at the top knows the person at the bottom, then move the top pointer down and vice versa.

If neither knows each other, then increment both pointer.

At the end, if the candidate at the top pointer is a celebrity.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;


int solution(vector<vector<int>> &arr)
{
    
    int n = arr.size();
    
    vector<int> peopleKnowMe(n, 0);
    
    vector<int> peopleIKnow(n, 0);
    
    for(int i=0; i < n; i++) 
    {
        for(int j=0; j < n; j++) 
        {
            
            if(arr[i][j] == 1) 
            {
                peopleKnowMe[j]++;
                peopleIKnow[i]++;
            }
        }
    }
    
    for(int i=0; i < n; i++) {
        
        if(peopleKnowMe[i] == n-1 && peopleIKnow[i] == 0) {
            return i;  
        }
    }
    
    return -1;
}

int solution_1(vector<vector<int>> &arr)
{
    
    int n = arr.size();
    
    int top = 0, down = n-1;
    
    // Traverse for all the people
    while(top < down) 
    {
        
        if(arr[top][down] == 1) 
        {
            top = top + 1;
        }
        
        else if(arr[down][top] == 1) 
        {
            down = down - 1;
        }
        
        else 
        {
            top++;
            down--;
        }
    }
    
    if(top > down) return -1;

    for(int i=0; i < n; i++) 
    {
        if(i == top) continue;
        
        if(arr[top][i] == 1 || arr[i][top] == 0) 
        {
            return -1;
        }
    }
    
    return top;
}


int main() {
    vector<vector<int>> arr = 
    {
         {0, 1, 1, 0}, 
         {0, 0, 0, 0}, 
         {1, 1, 0, 0}, 
         {0, 1, 1, 0}
    };
   
    
    cout << solution(arr)<<endl;
    cout << solution_1(arr)<<endl;
    
    return 0;
}

Output

1
1