Find the Celebrity

# Knows API already defined

def knows(a: int, b: int) -> bool:

# Solution

Note that it takes O(n)O(n) time to check if a person is a celebrity.

# Brute Force

Check if each person is a celebrity.


  • time: O(n2)O(n^2)
  • space: O(1)O(1)
def findCelebrity(self, n):
    for i in range(n):
        founded = True
        for j in range(n):
            if i==j:
            founded = founded and (knows(j,i) and not knows(i,j))
        if founded:
            return i
    return -1

# Logical Deduction

Let's ask this question: does A know B? If the answer is yes, then A is defo not a celebrity; o.w., B is not a celebrity. Thus, we could ask this question n-1 times and get a candidate for celebrity.

We then check if everyone else knows the candidate and the candidate knows no one else.


  • time: O(n)O(n)
  • space: $O(1)
def findCelebrity(self, n):
    candidate = 0

    for i in range(1,n):
        if not knows(i,candidate):
        ### above line could also be: ###
        # if knows(candidate,i):
            candidate = i
    # check if candidate is a celebrity
    for i in range(n):
        if i==candidate:
        if knows(candidate, i) or not knows(i, candidate):
            return -1
    return candidate
Last Updated: 7/19/2020, 3:45:14 PM