Find the Celebrity
Find the Celebrity is a medium graphs problem solved with the candidate elimination pattern.
The best approach, optimal (eliminate down to one candidate, then verify), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every person) up.
Problem
There are n people at a party, labelled 0 to n - 1. A celebrity is someone whom every other person knows, while the celebrity knows none of the others. There is at most one such person.
You cannot see who knows whom directly. Instead you get a helper knows(a, b) that returns true if person a knows person b. Implement findCelebrity(n) that returns the celebrity’s label, or -1 if there is no celebrity, using as few calls to knows as you can.
Examples
Example 1
- Input
n = 3, graph = [[1, 1, 0], [0, 1, 0], [0, 1, 1]]- Output
1- Why
- Persons 0 and 2 both know person 1, and person 1 knows nobody else.
Example 2
- Input
n = 3, graph = [[1, 0, 1], [1, 1, 0], [0, 1, 1]]- Output
-1- Why
- Everyone knows somebody else, so nobody qualifies.
Example 3
- Input
n = 4, graph = [[1, 0, 0, 1], [0, 1, 0, 1], [1, 0, 1, 1], [0, 0, 0, 1]]- Output
3- Why
- All three others know person 3, and person 3 knows no one else. Person 2 knowing person 0 does not matter.
Constraints
2 <= n <= 100graph[i][j]is0or1, andgraph[i][i] == 1.- You can only read the matrix through
knows(a, b), which returnstruewhen personaknows personb. - Aim for at most
3 * ncalls toknows.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check every person) | O(n^2) | O(1) |
| Optimal (eliminate down to one candidate, then verify) | O(n) | O(1) |
1Brute force (check every person)
O(n^2)Each of the n candidates may be checked against all n - 1 others, two calls each.O(1)Only loop counters.For each person, test the definition directly: they know nobody else, and everybody else knows them.
- For c = 0..n-1, for every other i: if knows(c, i) or !knows(i, c), c fails.
- Return the first c that never fails, or -1.
public class Solution extends Relation {
public int findCelebrity(int n) {
for (int c = 0; c < n; c++) {
boolean ok = true;
for (int i = 0; i < n && ok; i++) {
if (i == c) continue;
if (knows(c, i) || !knows(i, c)) ok = false;
}
if (ok) return c;
}
return -1;
}
}class Solution:
def findCelebrity(self, n: int) -> int:
for c in range(n):
ok = True
for i in range(n):
if i != c and (knows(c, i) or not knows(i, c)):
ok = False
break
if ok:
return c
return -1class Solution {
public:
int findCelebrity(int n) {
for (int c = 0; c < n; c++) {
bool ok = true;
for (int i = 0; i < n && ok; i++) {
if (i == c) continue;
if (knows(c, i) || !knows(i, c)) ok = false;
}
if (ok) return c;
}
return -1;
}
};function findCelebrity(n) {
for (let c = 0; c < n; c++) {
let ok = true;
for (let i = 0; i < n && ok; i++) {
if (i === c) continue;
if (knows(c, i) || !knows(i, c)) ok = false;
}
if (ok) return c;
}
return -1;
}2Optimal (eliminate down to one candidate, then verify)
O(n)n - 1 calls to pick the candidate plus at most 2(n - 1) calls to verify it.O(1)Only the candidate and a loop counter.Walk through the people keeping one candidate. If the candidate knows person i, the candidate cannot be the celebrity, and i becomes the new candidate; otherwise i cannot be the celebrity. After one pass only one person can still be the answer, so verify that person once.
- cand = 0; for i = 1..n-1: if knows(cand, i), cand = i.
- For every i != cand: if knows(cand, i) or !knows(i, cand), return -1.
- Return cand.
public class Solution extends Relation {
public int findCelebrity(int n) {
int cand = 0;
for (int i = 1; i < n; i++) if (knows(cand, i)) cand = i;
for (int i = 0; i < n; i++) {
if (i == cand) continue;
if (knows(cand, i) || !knows(i, cand)) return -1;
}
return cand;
}
}class Solution:
def findCelebrity(self, n: int) -> int:
cand = 0
for i in range(1, n):
if knows(cand, i):
cand = i
for i in range(n):
if i != cand and (knows(cand, i) or not knows(i, cand)):
return -1
return candclass Solution {
public:
int findCelebrity(int n) {
int cand = 0;
for (int i = 1; i < n; i++) if (knows(cand, i)) cand = i;
for (int i = 0; i < n; i++) {
if (i == cand) continue;
if (knows(cand, i) || !knows(i, cand)) return -1;
}
return cand;
}
};function findCelebrity(n) {
let cand = 0;
for (let i = 1; i < n; i++) if (knows(cand, i)) cand = i;
for (let i = 0; i < n; i++) {
if (i === cand) continue;
if (knows(cand, i) || !knows(i, cand)) return -1;
}
return cand;
}Edge cases to test
- No celebrity at all
- The celebrity is person 0 or person n - 1
- Everyone knows everyone (no celebrity)
- A candidate that everybody knows but who knows one person back
Hints
Hint 1
One call knows(a, b) rules out one of the two: if it is true, a is not the celebrity; if false, b is not.
Hint 2
So n - 1 calls can eliminate everyone except one candidate.
Hint 3
The last candidate is only a possible answer. Check it against every other person before returning it.
FAQ
What is the best time complexity for Find the Celebrity?
Optimal (eliminate down to one candidate, then verify) runs in O(n) time and O(1) extra space. n - 1 calls to pick the candidate plus at most 2(n - 1) calls to verify it.
Which pattern does Find the Celebrity use?
It is a graphs problem that uses the candidate elimination pattern.
Is there a brute force solution for Find the Celebrity?
Yes. Brute force (check every person) takes O(n^2) time and O(1) space. For each person, test the definition directly: they know nobody else, and everybody else knows them.
Which edge cases should I test for Find the Celebrity?
No celebrity at all; The celebrity is person 0 or person n - 1; Everyone knows everyone (no celebrity); A candidate that everybody knows but who knows one person back.