Last Updated on November 27, 2023 by Ankit Kochar
TThe Celebrity Problem in Java is a classic algorithmic puzzle that challenges programmers to efficiently identify a special individual within a group who is known by everyone but knows no one. This intriguing problem finds its applications in various fields, from network analysis to social media and even in real-world scenarios involving influential figures. As coders strive to devise optimal solutions to this problem, they encounter complexities that illuminate key concepts in algorithm design, graph theory, and computational efficiency.
Exploring the depths of the Celebrity Problem not only sharpens coding skills but also underscores the significance of problem-solving approaches and their practical implications. In this article, we will delve into the intricacies of the Celebrity Problem, examine different strategies to solve it, and understand its relevance in the realm of programming and beyond.
What is the Celebrity Problem in Java?
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.
Example of the Celebrity Problem
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 row = 1, all the elements are 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 maximum number of celebrities possible in a matrix. Consider the matrix shown below.
So, in the above matrix, there is no row with all elements 0 and, similarly, no column with all values 1 (except where row=col). As a result, the bare minimum of celebrities is 0.
Assume there are two celebrities in the matrix, X and Y. As a result, according to the definition of celebrity,
- Because X is a celebrity, X should not know Y, and Y should know X.
- Because Y is a celebrity, Y should not know X, and X should know Y.
Statement 1 states that X should not know Y, while Statement 2 states that S should know Y. These statements are diametrically opposed. 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 to Solve the Celebrity Problem
The basic approach is actually very intuitive. Let us represent the people in the party with the help of the 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 the 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 whose outdegree is 0 (the celebrity knows no one).
So, instead of constructing an actual graph, we can have two 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 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 it.
Code Implementation of the Celebrity Problem in Java
#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(n2) 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 to the Celebrity Problem using Stack
The time complexity of the previous solution was O(n2). 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.
We will now process the stack until only one element remains. We will take two elements from the stack at a time and push only one.
So, let us pop an element from the stack, and we’ll call it “col”. Let us select another element from the stack and label it "row." For the current iteration, col = 3 and row = 2.
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 out of 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.
We stop iterating now that there is only one element left in the stack. Again, this element is unlikely to be a celebrity. This is due to the fact that it was pushed into the stack not because it was a celebrity, but because the other element was not. As a result, we must examine this single element.
To do so, we traverse its row, and all of the elements should be 0. In addition, we traverse in its column, and all elements should be 1 (except where row=col).
In this instance, we discover that 1 is a celebrity. Now that we’ve grasped the procedure, let’s write the code for it.
Code Implementation of the Celebrity Problem using Stack
#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).
Conclusion
The Celebrity Problem presents a captivating challenge for programmers, requiring them to devise elegant algorithms to pinpoint a unique individual in a group with specific attributes. As we’ve explored various strategies, from brute force approaches to more optimized solutions using graph theory and elimination techniques, we’ve witnessed the evolution of problem-solving techniques.
Moreover, the significance of this problem transcends mere coding challenges; it reflects real-world scenarios where identifying influential entities within networks or communities holds considerable importance. By mastering this problem, programmers not only hone their algorithmic skills but also gain insights into broader applications across diverse domains.
As the quest for efficient algorithms continues, the Celebrity Problem serves as a testament to the intricate nature of problem-solving in coding and its relevance in understanding complex networks and relationships.
Frequently Asked Questions (FAQs) Related to The Celebrity Problem
Here are some FAQs related to the Celebrity Problem.
1. What is the Celebrity Problem in coding?
The Celebrity Problem involves identifying an individual within a group who is known by everyone but knows no one. In coding terms, it requires finding a person in a group where everyone else knows this person (the celebrity), but the celebrity doesn’t know anyone else.
2. What are the practical applications of solving the Celebrity Problem?
The problem has applications in various fields such as network analysis, social media, event scheduling, and even in identifying influential figures in different contexts.
3. What are some common strategies to solve the Celebrity Problem?
Strategies include brute force methods, graph-based algorithms like the graph elimination technique, and heuristic approaches that reduce the number of comparisons needed.
4. How does solving the Celebrity Problem contribute to coding skills?
Solving this problem sharpens algorithmic thinking, encourages optimization of solutions, and enhances understanding of graph theory and computational efficiency, which are crucial aspects of coding.
5. Can the Celebrity Problem be modified for different scenarios?
Yes, the problem can be adapted to various scenarios by altering the attributes or constraints of the individuals within the group, making it applicable to different real-world situations where similar identification challenges exist.
This article is amazing.