leetcode-array

277. Find the Celebrity.py

# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:

class Solution:
    """
    Problem Clarification: 
        Definition of celibrity:
            everbody knows him but he does not know anybody
    Thought Process:
        Brute Force
            Iterate all ppl in this party, for each ppl we iterate every possible candidate.
        Graph:
            On the graph representation, a celebrity is a person who has exactly n - 1 directed edges going in (everybody knows them) and 0 edges going out (they know nobody).
            
    Note:
        Follow up: If the maximum number of allowed calls to the API knows is 3 * n, could you find a solution without exceeding the maximum number of calls?

    """
    def findCelebrity(self, n: int) -> int:
        """
        Brute Force
        n * 2 * (n-1) calles
        """
        self.n = n
        for p in range(n):
            if self._is_celebrity(p):
                return p
        return -1
    
    def findCelebrity(self, n: int) -> int:
        """
        n-1 calles + 2 *(n-1) calls at most, 3n-3
        """
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if knows(celebrity_candidate, i):
                # if celebrity_candidate knows i, he's impossible to be a celebrity
                celebrity_candidate = i
        # if celebrity_candidate does not know any ppl, he might be a celebirty.
        if self._is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1
    
    def _is_celebrity(self, p):
        """
        this requires 2 *(n-1) calls. So, do meet requriements of follow-up
        """
        for candidate in range(self.n):
            if candidate == p:
                continue
            if knows(p, candidate) or not knows(candidate, p):
                return False
        return True