LC 0277 [M] Find the Celebrity
Code with Senpai edited this page Mar 24, 2022
·
1 revision
# 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)
footer