Straight forward C++ solution with explaination


  • 63
    H

    The idea is as follows:

    first, if person A knows person B, then B could be the candidate of being a celebrity, A must not be a celebrity. We iterate all the n persons and we will have a candidate that everyone knows this candidate.

    second, we check two things after we get this candidate. 1. If this candidate knows other person in the group, if the candidate knows anyone in the group, then the candidate is not celebrity, return -1; 2. if everyone knows this candidate, if anyone does not know the candidate, return -1;

    // Forward declaration of the knows API.

    bool knows(int a, int b);

    class Solution {

    public:

    int findCelebrity(int n) {
        if(n<=1) return n;
        
        int candidate = 0;
        
        for(int i=1; i<n; i++){
            
            if ( !knows(i,candidate) ){
                candidate = i;
            }
        }
        
       
        for(int j=0; j<n; j++){
            
            if(j== candidate) continue;
         
            if( !knows(j,candidate) || knows(candidate,j) ){
                  //if j does not know candidate, or candidate knows j, return -1;
                return -1;
            }
       
        }
       
        
        return candidate;
      
    }
    

    };


  • 1

    Good idea! But you seem to make a little mistake in the following words?

    if a person A does not know a person B, then B could be the candidate of being a celebrity, A must not be a celebrity.

    When A does not know B, the candidate should be A instead of B :-) Anyway, your code is really succinct :-)


  • 0
    H

    modified, thanks


  • 0

    Hi, @hbsophia. It seems that you've not included the following parts in your code :-)

    // Forward declaration of the knows API. bool knows(int a, int b);
    class Solution {
    public:

  • 0
    H

    modified that sentence, thanks !


  • 0
    S

    Brilliant solution. It would be nice to mention that the first run checks only if everyone AFTER the candidate knows him / her and need one more run to check if everyone BEFORE the candidate knows him.


  • 0
    O

    Could you explain why in the first pass, you won't miss possible candidate? Thanks!


  • 0

    Well, there can be at most one celebrity. So each time when we find someone is not the celebrity, we can just rule it out.


  • 0
    O

    @Jianchao.li.fighter, I understand we can simply rule not-celebrity out, but how do we ensure that the candidate after first pass is the right one to go pass 2?


  • 0

    The key is still that there can be at most one celebrity and since we rule out those non-celebrities, the remaining one is the only candidate that may be a celebrity. Try some examples and you will see it on your own.


  • 0
    F

    Good idea, just a slightly improvement, in the 2nd loop,
    from celebrity+1 to n, we don't need to call !knows(j,celebrity), since it's called in first loop.
    My AC code:

    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        cel=0
        for i in xrange(n):
            if not knows(i,cel):cel=i
            
        for i in xrange(cel):
            if not knows(i,cel):return -1
        
        for i in xrange(cel+1,n):
            if knows(cel,i):return -1
        return cel
    

  • 1
    C

    @fullmetal2000: for the following table, in which table[i][j]==1 means person i knows person j, your program will say celebrity is 3, but in reality, there is no celebrity. So I think you do still need to check if the candidate really does not know any one before him, although it is valid to skip checking on people after him for known(candidate, person)

    knownTable=[
        [1,1,1,1,0,0],
        [0,1,0,1,0,0],
        [0,0,1,1,0,0],
        [1,1,0,1,0,0],
        [0,0,0,1,1,0],
        [0,0,0,1,1,1]
        ]

  • 1
    Z

    I think it is Moore's Voting Algorithm of finding the Majority Element, in the first pass the person who is known by most other people stands out. Then we check whether everyone knows him and he knows no one in the second pass.


  • 0
    D

    optimized c++ code.
    I think it is better to understand this solution with graph theory. If there exists a celebrity, then this celebrity is the sink in this directed graph, so after the first for loop the candidate must end up as the sink node; otherwise, if there has no celebrity, candidate will end up as an invalid node.

    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 < candidate; i++) {  //do a for loop fission
                if(knows(candidate, i) || !knows(i, candidate)) return -1;
            }
            for(int i = candidate + 1; i < n; i++) {
                if(!knows(i, candidate)) return -1;
            }
            return candidate;
        }
    

  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0
    Z

    In the second loop, from j=candidate to n, you don't have to ask if knows(j, candidate) since you got the answers in the first loop. Here is the modified version, which saves questions and is a little faster.

    // Forward declaration of the knows API.
    bool knows(int a, int b);
    
    class 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(i, cand)) return -1;
            }
            for (int i=0;i<cand;i++){
                if (knows(cand, i)) return -1;
            }
            return cand;
        }
    };
    

  • 6
    M

    I summarize the thought using my own word and understanding:

    First we have two rules:

    Rule 1. If A knows B: A must not be celebrity, B possible
    Rule 2. If A doesn't know B: A possible, B must not be celebrity.

    Using Rule 2, we have the first loop: if i doesn't know candidate, we put i as our potential candidate of celebrity:

    for(int i=1; i<n; i++){
            
            if ( !knows(i,candidate) ){
                candidate = i;
            }
        }
    

    In this loop we know two things:

    1. Everything left of candidate ([0:candidates-1]) are not celebrity. (Because they 1. Either know someone or 2.They doesn't know anyone but someone doesn't know them as well!)
    2. Everything right of candidate ([candidates+1:n]) knows candidate (otherwise candidate will be j where j falls in [candidates+1,n])

    Notice that because of "2. Everything right of candidate ([candidates+1:n]) knows candidate ", we also conclude that everything right of candidate is not celebrity, proved by Rule 1. So from the first loop, the conclusion we can make is :

    Every other person besides candidate MUST NOT be celebrity.

    So now we just need to find out whether this candidate is celebrity, if it is, then it is; if not, then no one is celebrity in this party.

    So we have the second loop whose only purpose is to find whether candidate is the celebrity. That's it.

    Hope my explanation helps a little bit. :)


Log in to reply
 

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