Solution in C#


  • 0
    P

    The key to solving this problem is returning as soon as you know whether someone is a celebrity or not, and skipping to the next person as soon as you find someone that knows them.

    Saving a bit of time is the observation that a single call to Knows(a,b) always excludes a person from future consideration. Why? Because if a knows b, then a is not a celeb. If a doesn't know b, then b is not a celeb (because everyone else has to know the celeb).

    Since you must check, at most, every person, loop over them until you get a failure case, or exhaust the list of potential fans.

    There are 2 failure cases for celebrity:

    • another person (the fan) doesn't know the person p
    • p knows a fan

    Once either of those failure cases happens, you can skip to the next candidate. If neither happened, then you know all of the other people knew p, so you can immediately return p.

    If you reach the end of the list of people without finding a celebrity, then none are, so return -1.
    Given this set of people:
    0_1521185469496_WhoIsTheCelebrity.png
    We see the following calls to Knows(a,b):

    0: Knows(0, 1) = true (not a celebrity)
    1: Knows(1, 0) = true (not a celebrity)
    2: 2x calls with Knows(2, [0,1]) = false, 3x calls to Knows([0,1,3], 2) = true, no more people to check so return 2. This is our celebrity!
    3: skipped

    O(n) overall time complexity
    O(n) space complexity.

    public int FindCelebrity(int n)
    {
        if (n <= 1)
            return -1;
    
        var excluded = new bool[n]; // initialized to false!
                
        // Loop over all the people.
        for (int p = 0; p < n; p++)
        {
            if (excluded[p]) continue;
            bool failed = false;
    
            for (int fan = 0; fan < n; fan++)
            {
                if (p == fan) continue;
    
                if (Knows(p, fan))
                {
                    excluded[p] = true;
                    failed = true;
                    break;
                }
                else
                {
                    // someone doesn't know the fan, so that fan is excluded
                    excluded[fan] = true;
                }
                if (!Knows(fan, p))
                {
                    failed = true;
                    break;
                }
                else
                {
                    // the fan knows someone, so fan is excluded from consideration as a celeb
                    excluded[fan] = true;
                }
            }
    
            if (!failed)
                return p;
        }
        return -1;
    }
    

Log in to reply
 

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