Java Solution. Two Pass


  • 202
    C

    The first pass is to pick out the candidate. If candidate knows i, then switch candidate. The second pass is to check whether the candidate is real.

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

  • 0
    Y
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 4
    N

    I like the way you select candidate!!


  • 0
    This post is deleted!

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

    This can also work.


  • 5
    5

    Correct me if I am wrong. I think the second loop may do duplicated calls to knows(). Maybe it can be optimized to reduce the number of calls to knows();


  • 3

    Yes you are right.
    The calls "knows(candidate,i)" with i > candidate in the second loop is not necessary.
    But asymptoticly it is the same. Also in worse case scenario, candidate can be n-1 after first loop, thus make this optimization gain nothing.


  • 5
    H

    In my understanding, your first pass uses a loose check. For example, if we got a person in the n-1 th index that doesn't know everyone in party, nor did anyone know him. Then the candidate winner from 0 to n-2th will still be valid. But this error will be caught in your second pass which is more strict. So we can't stop at the index that candidate is found. Correct me if I am wrong


  • 12
    S

    How about if someone knows no one, but only part of others know him/her? In this case he/she will pass the first pass. And if the index of real 'Celebrity' is bigger than that guy, the first pass will return that guy instead of real 'Celebrity'. The 2nd pass will return -1 even 'Celebrity' exists.
    Correct me if I am wrong.


  • 0
    E

    awesome solution!


  • 0
    J

    can you explain more on what's idea behind selecting the candidate? Thanks!


  • 9
    E

    If someone S knows no one, either S is the celebrity or this isn't one. Because every one , including S must know celebrity if it is not S him/herself.


  • 157
    E

    Brilliant algorithm. For those who have problem understanding it, the following is my understanding:

    The first loop is to find the candidate as the author explains. In detail, suppose the candidate after the first for loop is person k, it means 0 to k-1 cannot be the celebrity, because they know a previous or current candidate. Also, since k knows no one between k+1 and n-1, k+1 to n-1 can not be the celebrity either. Therefore, k is the only possible celebrity, if there exists one.

    The remaining job is to check if k indeed does not know any other persons and all other persons know k.

    To this point, I actually realize that we can further shrink the calling of knows method. For example, we don't need to check if k knows k+1 to n-1 in the second loop, because the first loop has already done that.

    The optimized code is as follows:

    public int findCelebrity(int n) {
        int candidate = 0;
        for(int i = 1; i < n; i++){
            if(knows(candidate, i))
                candidate = i;
        }
        for(int i = 0; i < n; i++){
            if(i<candidate && knows(candidate, i) || !knows(i, candidate)) return -1;
            if(i>candidate && !knows(i, candidate)) return -1;
        }
        return candidate;
    }

  • 0
    M
    This post is deleted!

  • 0
    S

    Thanks for the explanation.


  • 0
    S

    Let's say i = k, you first time switch candidate, then 0 ~ k -1 will not have candidate. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. So if the pre candidate(0) doesn't know 1 ~ k-1, then 1 ~ k - 1 are not celebrity. As you just switch candidate, then 0 is not.


  • 0
    D

    smart way to modify


  • 0
    I

    How do u know that everyone from 0 to k-1 knows the celebrity at k?


  • 1
    R

    You don't know, that's why the second pass is there. But you do know that there is no celebrity in 0 to k-1, so if there is a celebrity, it has to be k.


Log in to reply
 

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