The Celebrity Problem

Problem Statement

There is a party of N (numbered 0 to N-1) people. There might or might not be a celebrity at this party. A celebrity is someone who is known to everyone but does not know anyone. So, if you are a celebrity at a party, you will be known to everyone but, you won’t know anyone there.

This situation is represented in the form of an N x N binary matrix. So, every cell can either have a value of 0 or 1. If matrix[i][j] = 1, this means that the ith person knows the jth person.

You have to tell whether a celebrity is present at the party or not. If it is present, we also have to tell which element (person) is the celebrity.

Note: The elements of the diagonal i.e. when i=j are always set to 0.

Examples

Let us consider the binary matrix shown below.

So, in the above matrix, 1 is the celebrity. This is because the row with index 1 has all elements 0 which means that 1 does not know anyone and the column with index 1 has all the elements 1 (except where row=column=1) which means that every element (every person in the party) knows 1. Let us consider some more examples.

In the above matrix, there is a column (column 1) that has all the elements 1 (except row=col) however, row 1 has a 1 in it at column 2. This means that 1 knows 2. So, 1 cannot be a celebrity. In fact, there is no celebrity in the matrix.

In another case, when we have the row=1 having all the elements 0. However, in this case, column=1 does not have all the elements 1. The element at row=2 is 0 meaning 2 does not know 1. Hence, 1 cannot be a celebrity. In fact, there is no celebrity in this matrix.

How many Celebrities are possible in a Matrix?

Before we jump into solving the problem, a very genuine question to ask is the minimum and a maximum number of celebrities possible in a matrix. Consider the matrix shown below.

So, in the above matrix, there is no row with all the elements 0 and corresponding to it, we don’t have a column with all values 1 (except where row=col). Hence, the minimum number of celebrities possible is 0.

Now, let us say that there are 2 celebrities in the matrix X and Y. So, according to the definition of a celebrity,

  1. X should not know Y and Y should know X since X is a celebrity.
  2. Y should not know X and X should know Y since Y is a celebrity.

In statement 1, we say that X should not know Y and in statement 2, we say that S should know Y. These statements are contradicting each other. Hence, our assumption that there are 2 celebrities in the matrix is never possible.

So, the maximum number of celebrities possible in a matrix is 1.

Basic Approach

The basic approach is actually very intuitive. Let us represent the people in the party with the help of vertices (nodes) of a graph. An edge from vertex V1 to V2 means V1 knows V2.

Now, consider the matrix that is shown below and the graph corresponding to it.

So, in the matrix, we can see that matrix[0][1] = 1 and matrix[0][2] = 1. This means that 0 knows 1 and 2. This is shown in the graph by directed edges from vertex 0 to vertices 1 and 2 respectively.
Similarly, the entire graph is created by traversing the matrix once. So, a celebrity in this case will be a vertex whose indegree is V-1 (everyone knows the celebrity) where V is the total number of vertices and its outdegree will be 0 (celebrity knows no one).

So, instead of constructing an actual graph, we can have 2 arrays of size V representing the indegree and outdegree of each vertex respectively. So, let us consider the situation shown below.

So, we have 2 arrays, in and out for the matrix. As shown, initially, they are filled with 0s. Now, let us traverse the 1st row of the matrix.

Since matrix[0][0] = 0, this means that currently, there is no edge. Since diagonal elements are 0, there will not be any self-loops in the graph.

Now, let us move to the next index.

Since matrix[0][1] = 1, this means that there should be an edge from 0 to 1. This means that the outdegree of 0 should increase by 1 and the in-degree of 1 should increase by 1. So, the conclusion that we derive from this is shown below.

So, we can traverse the entire matrix and fill the array using this condition.

Now, just traverse the arrays and find if for any vertex i, in[i] = V-1 and out[i] = 0. If found, this ith vertex will be the celebrity.
In this case, it is vertex 1.

Now that we have understood this method, let us write the code for the same.

Code Implementation

#include <bits/stdc++.h> 
using namespace std; 
int celebrity_solution(int mat[][4], int n) {
    int in[n];
    int out[n];
    for(int i=0;i<n;i++) {
        in[i] = out[i] = 0;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(mat[i][j] == 1) {
                out[i]++;
                in[j]++;
            }
        }
    }
    for(int i=0;i<n;i++) {
        if(in[i] == n-1 && out[i] == 0) return i;
    }
    return -1;
}
int main() {
    int matrix[][4] = {{0,1,1,0},
                     {0,0,0,0},
                     {0,1,0,0},
                     {1,1,0,0}};
    int res = celebrity_solution(matrix,4);
    if(res == -1) {
        cout<< "There is no celebrity in the party";
    } else {
        cout<< res <<" is the celebrity in the party";
    }
}

import java.util.*;
public class Main {
    public static int celebritySolution(int[][] mat) {  
        int V = mat.length;
        int[] in = new int[V];
        int[] out = new int[V]; 
        for(int i=0;i<V;i++) {
            for(int j=0;j<V;j++) {
                if(mat[i][j] == 1) {
                    out[i]++;
                    in[j]++;
                }
            }
        }
        for(int i=0;i<V;i++) {
            if(in[i] == V-1 && out[i] == 0) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[][] matrix = {{0,1,1,0},
                         {0,0,0,0},
                         {0,1,0,0},
                         {1,1,0,0}};                 
        int res = celebritySolution(matrix);
        if(res == -1) {
            System.out.println("There is no celebrity in the party");
        } else {
            System.out.println(res + " is the celebrity in the party");
        }
    }
}

Time Complexity: The time complexity of the above approach is O(n^2) because of the matrix traversal.

Space Complexity: O(n) as we have created 2 auxiliary arrays of size n where n is the number of people in the party.

Optimized Approach

The time complexity of the previous solution was O(n^2). We can write a solution in O(n) time without using a graph and instead using a stack.

Consider the matrix that is shown below and a Stack of Integers as shown.

Let us push all the elements (people at the party) into the stack. Here, the order does not matter.

Now, we will process the stack till only 1 element remains inside it. We will pop 2 elements from the Stack at a time and push only 1 element.

So, let us pop an element from the stack and we call it “col”. Let us pop another element from the stack and we call it “row”. So, col = 3 and row = 2, for current iteration.

Now, we check whether matrix[row][col] = 1 or 0. Here, matrix[row][col] = matrix[2][3] = 0. This means that 2 does not know 3. Since a celebrity is a person known to everyone, it is sure that 3 will not be a celebrity. However, 2 may or may not be a celebrity. Hence, we push 2 back into the stack.

So, the conclusion devised from the above observation is shown below.

Again, let us continue the steps. So, we pop again from the stack as shown.

So, again, the column will be discarded and we will push the row into the stack.

Again, let’s pop from the stack.

Since matrix[0][1] = 1, this means that 0 knows 1. A celebrity is an element that does not know anyone. Since 0 knows 1, it cannot be a celebrity. Hence, we will discard it.

The conclusion is shown below.

Now that only 1 element is left in the stack, we stop the iteration. Again, this element is not surely a celebrity. This is because when it got pushed into the stack, it was not because it was a celebrity, but rather because the other element was not. Hence, we need to check this single element.

For that, we traverse in its row and all the elements should be 0. Also, we traverse in its column and all the elements should be 1 (except where row=col).

In this case, we find that 1 is a celebrity.

Now that we have understood the procedure, let us write the code for the same.

Code Implementation

#include <bits/stdc++.h> 
using namespace std; 
  
int celebrity_solution(int mat[][4],int N) {
        stack<int> stk;
    	
    	for(int i=0;i<N;i++) {
    	    stk.push(i);
    	}
    	
    	while(stk.size() > 1) {
    	    int col = stk.top();
    	    stk.pop();
    	    int row = stk.top();
    	    stk.pop();
    	    if(mat[row][col] == 1) {
    	        stk.push(col); //col may or may not be a celeb
    	    } else {
    	        stk.push(row); //row may or may not be a celeb
    	    }
    	}
    	
    	int x = stk.top();
    	stk.pop();
    	
    	for(int j=0;j<N;j++) {
    	    if(j == x) continue;
    	    if(mat[x][j] == 1) {
    	        return -1;
    	    }
    	}
    	
    	for(int i=0;i<N;i++) {
    	    if(i == x) continue;
    	    if(mat[i][x] == 0) {
    	        return -1;
    	    }
    	}
    	
    	return x;
}  
  
int main() {
    int matrix[][4] = {{0,1,1,0},
                     {0,0,0,0},
                     {0,1,0,0},
                     {1,1,0,0}};
                     
    int res = celebrity_solution(matrix,4);
    if(res == -1) {
        cout<< "There is no celebrity in the party";
    } else {
        cout<< res <<" is the celebrity in the party";
    }
}
import java.util.*;

public class Main {
    
    public static int celebritySolution(int[][] mat) {
        Stack<Integer> stk = new Stack<>();
    	
    	for(int i=0;i<mat.length;i++) {
    	    stk.push(i);
    	}
    	
    	while(stk.size() > 1) {
    	    int col = stk.pop();
    	    int row = stk.pop();
    	    if(mat[row][col] == 1) {
    	        stk.push(col); //col may or may not be a celeb
    	    } else {
    	        stk.push(row); //row may or may not be a celeb
    	    }
    	}
    	
    	int x = stk.pop();
    	
    	for(int j=0;j<mat.length;j++) {
    	    if(j == x) continue;
    	    if(mat[x][j] == 1) {
    	        return -1;
    	    }
    	}
    	
    	for(int i=0;i<mat.length;i++) {
    	    if(i == x) continue;
    	    if(mat[i][x] == 0) {
    	        return -1;
    	    }
    	}
    	
    	return x;
    }
    
    public static void main(String[] args) {
          int[][] matrix = {{0,1,1,0},
                         {0,0,0,0},
                         {0,1,0,0},
                         {1,1,0,0}};
                         
        int res = celebritySolution(matrix);
        if(res == -1) {
            System.out.println("There is no celebrity in the party");
        } else {
            System.out.println(res + " is the celebrity in the party");
        }
    }
}

Time Complexity: The time complexity of this solution is O(N). This is because the maximum height of the Stack is also O(N) and for checking whether the last element is a celebrity or not, we are traversing just 1 row and 1 column. So, the time complexity becomes O(N + N) = O(2N) = O(N) only.

Space Complexity: The space complexity is O(N). This is because we are using a stack with maximum height = O(N).

So, this is how we can determine whether there is a celebrity at the party or not. Hope you liked the discussion.

Follow up: Can the same optimized approach be done using Recursion? Think about it !!!

This article tried to discuss The Celebrity Problem. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.

One thought on “The Celebrity Problem

Leave a Reply

Your email address will not be published. Required fields are marked *