The Celebrity Problem: Efficient Algorithm Solution
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
In a party of n people, a "celebrity" is defined as someone who:
- Doesn't know anyone at the party
- Everyone else at the party knows the celebrity
Your task is to find the celebrity in the party (if one exists). You are given a helper function knows(A, B) which returns true if person A knows person B, and false otherwise.
The problem can be represented using an n×n matrix where:
- matrix[i][j] = 1 if person i knows person j
- matrix[i][j] = 0 if person i doesn't know person j
Note that a person cannot know themselves, so matrix[i][i] = 0 for all i.
Brute Force Approach
Explanation
The simplest way to solve this problem is to check each person and verify if they meet both celebrity conditions:
- They don't know anyone (all zeros in their row)
- Everyone knows them (all ones in their column, except the diagonal element)
For each person, we'll need to scan an entire row and column of the matrix, making this approach straightforward but not very efficient.
The brute force approach has:
- Time Complexity: O(n²) since for each of the n people, we check n-1 relationships
- Space Complexity: O(1) as we only use a constant amount of extra space
Here P2 is a celebrity .
Python Code
def findCelebrity(n, knows):
# Helper function to check if person i is a celebrity
def isCelebrity(i):
# Check if i knows anyone
for j in range(n):
if i != j and knows(i, j):
return False # i knows someone, so not a celebrity
# Check if everyone knows i
for j in range(n):
if i != j and not knows(j, i):
return False # Someone doesn't know i, so not a celebrity
return True # i meets both celebrity conditions
# Check each person
for i in range(n):
if isCelebrity(i):
return i # Found the celebrity
return -1 # No celebrity exists
C++ Code
int findCelebrity(int n, function<bool(int, int)> knows) {
// Helper function to check if person i is a celebrity
auto isCelebrity = [&](int i) {
// Check if i knows anyone
for (int j = 0; j < n; j++) {
if (i != j && knows(i, j)) {
return false; // i knows someone, so not a celebrity
}
}
// Check if everyone knows i
for (int j = 0; j < n; j++) {
if (i != j && !knows(j, i)) {
return false; // Someone doesn't know i, so not a celebrity
}
}
return true; // i meets both celebrity conditions
};
// Check each person
for (int i = 0; i < n; i++) {
if (isCelebrity(i)) {
return i; // Found the celebrity
}
}
return -1; // No celebrity exists
}
Java Code
// The knows API is defined in the parent class
// boolean knows(int a, int b);
public int findCelebrity(int n) {
// Helper function to check if person i is a celebrity
Predicate<Integer> isCelebrity = i -> {
// Check if i knows anyone
for (int j = 0; j < n; j++) {
if (i != j && knows(i, j)) {
return false; // i knows someone, so not a celebrity
}
}
// Check if everyone knows i
for (int j = 0; j < n; j++) {
if (i != j && !knows(j, i)) {
return false; // Someone doesn't know i, so not a celebrity
}
}
return true; // i meets both celebrity conditions
};
// Check each person
for (int i = 0; i < n; i++) {
if (isCelebrity.test(i)) {
return i; // Found the celebrity
}
}
return -1; // No celebrity exists
}
Optimized Approach
Explanation
We can optimize this solution by using the fact that if A knows B, then A cannot be the celebrity. Similarly, if A doesn't know B, then B cannot be the celebrity.
The optimized strategy works in two phases:
- Elimination phase: Find a potential celebrity candidate
- Start with person 0 as the candidate
- For each other person i:
- If the candidate knows i, then the candidate cannot be a celebrity, so i becomes the new candidate
- If the candidate doesn't know i, then i cannot be a celebrity, so the candidate remains the same
- Verification phase: Verify if the candidate is actually a celebrity
- Check if the candidate knows no one
- Check if everyone knows the candidate
This approach reduces the number of calls to the knows function significantly.
The optimized approach has:
- Time Complexity: O(n) as we make at most 3n calls to the knows function
- Space Complexity: O(1) as we only use a constant amount of extra space
Let's Consider The Following example,
We start with 4 candidates (0-3) and need to find the best match based on compatibility with 4 people (0-3). Y means compatible, N means not compatible.
We Assume Celebrity be Zero,
Then Zero Knows One,So candidate = 1,
One knows two, So candidate = 2,
Two knows Three ,so Candidate = 3.
Lets Verify if 3 is a Celebrity.
We Can see Three knows 0,1,2 so 3 can’t be celebrity so there is no celebrity in this case.
Celebrity Problem Visualization
<visualization-box>
Python Code
def findCelebrity(n, knows):
# Phase 1: Find a potential celebrity candidate
candidate = 0
for i in range(1, n):
if knows(candidate, i):
# If candidate knows i, candidate cannot be a celebrity
# i becomes the new candidate
candidate = i
# Phase 2: Verify the candidate
# Check if candidate knows no one
for i in range(n):
if i != candidate and knows(candidate, i):
return -1 # Candidate knows someone, so not a celebrity
# Check if everyone knows the candidate
for i in range(n):
if i != candidate and not knows(i, candidate):
return -1 # Someone doesn't know the candidate, so not a celebrity
return candidate # Found the celebrity
C++ Code
#include <functional>
int findCelebrity(int n, std::function<bool(int, int)> knows) {
// Phase 1: Find a potential celebrity candidate
int candidate = 0;
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) {
// If candidate knows i, candidate cannot be a celebrity
// i becomes the new candidate
candidate = i;
}
}
// Phase 2: Verify the candidate
// Check if candidate knows no one
for (int i = 0; i < n; i++) {
if (i != candidate && knows(candidate, i)) {
return -1; // Candidate knows someone, so not a celebrity
}
}
// Check if everyone knows the candidate
for (int i = 0; i < n; i++) {
if (i != candidate && !knows(i, candidate)) {
return -1; // Someone doesn't know the candidate, so not a celebrity
}
}
return candidate; // Found the celebrity
}
Java Code
// The knows API is defined in the parent class
// boolean knows(int a, int b);
public int findCelebrity(int n) {
// Phase 1: Find a potential celebrity candidate
int candidate = 0;
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) {
// If candidate knows i, candidate cannot be a celebrity
// i becomes the new candidate
candidate = i;
}
}
// Phase 2: Verify the candidate
// Check if candidate knows no one
for (int i = 0; i < n; i++) {
if (i != candidate && knows(candidate, i)) {
return -1; // Candidate knows someone, so not a celebrity
}
}
// Check if everyone knows the candidate
for (int i = 0; i < n; i++) {
if (i != candidate && !knows(i, candidate)) {
return -1; // Someone doesn't know the candidate, so not a celebrity
}
}
return candidate; // Found the celebrity
}
Conclusion
The Celebrity Problem teaches important lessons about using problem constraints to optimize solutions. By recognizing that a celebrity must follow specific relationship patterns, we reduced the time complexity from O(n²) to O(n).
The key insight was that we could eliminate candidates efficiently: if A knows B, A cannot be the celebrity; if A doesn't know B, B cannot be the celebrity. This logical deduction allowed us to find a potential candidate with just n-1 comparisons.
