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


  • 65

    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.


  • 0
    Z

    Thank you for the elegant solution and detailed explanation.


  • 0
    R

    third loop

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


  • 0
    W

    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
    

  • 1

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


  • 0
    F

    @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).


  • 4
    L

    @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


  • 1
    Y
    This post is deleted!

  • 1
    Z

    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?


  • 0
    T

    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.


  • 0
    W

    @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.


Log in to reply
 

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