Java/Python, O(n) calls, O(1) space easy to understand solution

• Java

``````public class Solution extends Relation {
public int findCelebrity(int n) {
int x = 0;
for (int i = 0; i < n; ++i) if (knows(x, i)) x = i;
for (int i = 0; i < x; ++i) if (knows(x, i)) return -1;
for (int i = 0; i < n; ++i) if (!knows(i, x)) return -1;
return x;
}
}

// 171 / 171 test cases passed.
// Status: Accepted
// Runtime: 13 ms
// 97.79%
``````

Python

``````def findCelebrity(self, n):
x = 0
for i in xrange(n):
if knows(x, i):
x = i
if any(knows(x, i) for i in xrange(x)):
return -1
if any(not knows(i, x) for i in xrange(n)):
return -1
return x

# 171 / 171 test cases passed.
# Status: Accepted
# Runtime: 1460 ms
# 91.18%
``````

Explanation

The first loop is to exclude `n - 1` labels that are not possible to be a celebrity.
After the first loop, `x` is the only candidate.
The second and third loop is to verify `x` is actually a celebrity by definition.

The key part is the first loop. To understand this you can think the `knows(a,b)` as a `a < b` comparison, if `a` knows `b` then `a < b`, if `a` does not know `b`, `a > b`. Then if there is a celebrity, he/she must be the "maximum" of the `n` people.

However, the "maximum" may not be the celebrity in the case of no celebrity at all. Thus we need the second and third loop to check if `x` is actually celebrity by definition.

The total calls of knows is thus `3n` at most. One small improvement is that in the second loop we only need to check i in the range `[0, x)`. You can figure that out yourself easily.

• Thank you for the elegant solution and detailed explanation.

• third loop

for(int i = n-1 ; i > x; i--){
if(!knows(i,x))
return -1;
}

• Great code! Not sure if the first loop was a typo, but here is what might be a corrected version. Can someone clarify if these corrections are better, or if the original intended for the first check to be non-exhaustive?

Basically the first check only covers 0-x instead of 0-n, and also don't check if the celebrity knows themselves since this implies nothing

``````def findCelebrity(self, n):
x = 0
for i in xrange(n):
if knows(x, i):
x = i
if any(knows(x, i) for i in xrange(n) if i != x):
return -1
if any(not knows(i, x) for i in xrange(n) if i != x):
return -1
return x
``````

• I like the way you explain the knows function. consider knows(a,b) as a<b makes the problem much easier.

• @readman This was intentional. The first loop reads: if at any point (starting at x = 0) x knows someone (i), then i is the celebrity and x = i. To check if x is the celebrity, you have to confirm:

(1) x doesn't know anyone who claimed they knew them (the range [0, x - 1] from the first loop) and
(2) everyone after them knows who they are (the remaining range [x + 1, n]).

So, in response to @dietpepsi's solution, I would also reduce the range of the second check loop to [x + 1, n] because [0, n] redundantly includes range [0, x], where we know x to be the celebrity and everyone before x to have designated x as the celebrity (from the first loop).

• @fad93 Take the case 2 is the celebrity in [0,1,2,3]

The first loop gives 0 knows 1, 1 knows 2, 2 does not know 3.
Second loop gives 2 does not know 0, 2 does not know 1
What your third loop is saying is: 3 knows 2. What we dont know is if 0 knows 2 so we have to check the entire n. You can't assume that 0 knows 2 just because 0 knows 1 and 1 know 2

• This post is deleted!

• I have a concern for the second loop.
for example: 0 1 2 3,
in this: 0 knows 1, 1 knows 2, 2 doesn't know 3.
in the second loop, you only judged whether 2 knows 0 and 1, but it is still possible that 0 doesn't know 2.

So, is there a problem?

• The first loop will stop to an candidate i who doesn't know anyone from i+1 to n-1. For any previous x<i either know sb else or is not known by sb else.

The second loop will check whether i knows anyone from 0 to i-1.

The third loop is gonna check whether all party participants know x or not.

• @livelearn I have the same concern. Since this solution passed the test, I guess here we assume that 0->1, 1->2, then 0->2.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.