Python. Two Pass w/ Explaination.


  • 0
    def findCelebrity(self, n):
        # if just one person or no person, then no celeb
        if n in (0, 1):
            return -1
        slow, fast = 0, 1
        while fast < n:
            # if slow doesn't know fast, then fast cannot be a celeb
            if not knows(slow, fast):
                fast += 1
            # slow knows fast, so every thing from slow up to but not including fast cannot be a celeb
            else:
                slow = fast
                fast += 1
        # at this point, slow is our only possible celeb. Just loop through everyone and check if slow satisfies our reqs.
        for i in range(n):
            if i == slow:
                continue
            if not knows(i, slow) or knows(slow, i):
                return -1
        return slow
    

Log in to reply
 

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