Problem Statement
A celebrity is a person who:
- Knows no one.
- Is known by everyone else.
Given an N × N matrix:
M[i][j] = 1
→ i knows j
Find the celebrity.
Return:
Celebrity Index
OR
-1
if no celebrity exists.
Brute Force Intuition
In an interview, you can explain it like this:
Check every person individually. Verify whether they know nobody and everybody else knows them.
This requires checking an entire row and column for every person.
Complexity
- Time Complexity: O(N²)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public int celebrity(int[][] M, int n) {
for (int i = 0; i < n; i++) {
boolean celebrity = true;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (M[i][j] == 1 ||
M[j][i] == 0) {
celebrity = false;
break;
}
}
if (celebrity)
return i;
}
return -1;
}
}
Moving Towards the Optimal Approach
Notice an important observation.
Suppose:
A knows B
Then:
A
Cannot be Celebrity
Similarly,
If:
A does NOT know B
Then:
B
Cannot be Celebrity
So with one comparison,
we eliminate one candidate.
Pattern Recognition
Whenever you see:
- Eliminate Candidates
- Pairwise Comparison
- Find One Possible Answer
Think:
Two Pointers / Elimination
Key Observation
Start with:
Person 0
Person N-1
Compare:
Does Left Know Right ?
YES
Left Cannot Be Celebrity
Move Left++
NO
Right Cannot Be Celebrity
Move Right--
Eventually,
only one candidate survives.
Now simply verify.
Optimal Approach
Step 1
Keep:
left = 0
right = n-1
Step 2
If:
M[left][right] == 1
Move:
left++
Else:
right--
Step 3
One candidate remains.
Verify:
- Entire Row
- Entire Column
Optimal Java Solution
class Solution {
public int celebrity(int[][] M, int n) {
int left = 0;
int right = n - 1;
while (left < right) {
if (M[left][right] == 1) {
left++;
} else {
right--;
}
}
int candidate = left;
for (int i = 0; i < n; i++) {
if (i == candidate)
continue;
if (M[candidate][i] == 1 ||
M[i][candidate] == 0) {
return -1;
}
}
return candidate;
}
}
Dry Run
Input
0 1 2
0 → [0 1 1]
1 → [0 0 1]
2 → [0 0 0]
Step 1
Left = 0
Right = 2
Check:
0 knows 2
YES
Move:
Left = 1
Step 2
Check:
1 knows 2
YES
Move:
Left = 2
Candidate:
2
Verification
Row:
0 0 0
Knows nobody ✓
Column:
1
1
0
Everyone knows 2 ✓
Answer:
2
Why Two Pointers Work?
Every comparison removes exactly one person from consideration.
After:
N-1 comparisons
only one possible celebrity remains.
The final verification confirms whether that candidate satisfies the celebrity conditions.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(1) |
Interview One-Liner
Eliminate one candidate in every comparison using two pointers, then verify the remaining candidate by checking its row and column.
Pattern Learned
Pairwise Elimination
↓
One Candidate Left
↓
Verify Candidate
Similar Problems
- Celebrity Problem
- Find the Judge (LeetCode)
- Gas Station
- Majority Element
- Boyer-Moore Voting Algorithm
Memory Trick
Think:
A Knows B ?
↓
Yes
↓
A Cannot Be Celebrity
-------------------
No
↓
B Cannot Be Celebrity
Mental Model
Compare Two People
↓
Eliminate One
↓
Repeat
↓
One Candidate Left
↓
Verify
Whenever you hear:
"Find the celebrity"
your brain should immediately think:
Candidate Elimination + Verification