LC 0277 [M] Find the Celebrity - ALawliet/algorithms GitHub Wiki

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

class Solution:
    # O(n^2), O(1)
    def findCelebrity(self, n: int) -> int:
        self.n = n
        for i in range(n):
            if self.is_celebrity(i):
                return i
        return -1
    
    # O(n), O(1)
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        # find celebrity candidate first (this is the important trick)
        # if a knows b, then a cannot be a celebrity, and b is the new candidate
        for b in range(n):
            if self.cachedKnows(celebrity_candidate, b):
                celebrity_candidate = b
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1
    
    def is_celebrity(self, a):
        # celebrity does not know anyone and everyone knows them
        for b in range(self.n):
            if a == b: continue # don't need to check if someone knows themselves
            if self.cachedKnows(a, b) or not self.cachedKnows(b, a): # check both directions 
                return False
        return True
    
    # not necessary but makes it even faster
    @lru_cache(maxsize=None)
    def cachedKnows(self, a, b):
        return knows(a, b)