Task here is to find out who the celebrity is from n number of people. The predicates that need to be considered is that:
A celebrity knows no one
A celebrity is known by everyone but themselves
A time complexity of O(n) needs to be achieved
Additionally we are given a function called knows that will tell us if a knows b through a unidirectional manner.
Additionally, one key challenge here is that we minimize the number of times we call the knows API, such that we do not utilize it similar to how we would in the brute force approach.
Solution Explanation
There are two distinct solutions to this problem, one way is by brute forcing it whereas the other is by simply following a strategic algorithm.
If we were to brute force the problem it would mean that we consider all the possible knows between each person to formulate a graph that shows us how many people know each other. However, the down side to this is that it will have a time complexity of O(n).
So, the more ideal solution would be the following:
We can setup an algorithm where we create a search pattern that works on these two negative predicates:
If a person is not known by someone, they are outed as a potential candidate
If a person knows someone else, they are outed as a potential candidate
Knowing this we can go ahead and carry out a linear search where we go through each person, check to see if they know the person ahead of them, if they do we switch to them as the potential candidate, then we move to the next and if we do not know them, we do not switch candidates given that that person is not known by us hence making them something we do not consider.
We can implement the solution through the following pattern:
Implementation
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
numberOfPeople = 0
def findCelebrity(self, n: int) -> int:
self.numberOfPeople = n
celebrityCandidate = 0 # start with 0
for i in range(n):
if (knows(celebrityCandidate, i)): # if 0 knows someone else
celebrityCandidate = i # switch to them
if self.isCelebrity(celebrityCandidate):
return celebrityCandidate # check to see if celeb
return -1
def isCelebrity(self,i: int) -> bool: # brute force approach per person
for j in range(self.numberOfPeople):
if (i==j):
continue
if (knows(i,j) or not knows(j,i)):
return False
return True
The pseudocode would look something like this:
FUNCTION findCelebrity(n):
Set numberOfPeople = n
Set celebrityCandidate = 0
FOR i IN RANGE(n):
IF (knows(celebrityCandidate, i)):
celebrityCandidate = i
ENDIF
ENDFOR
IF isCelebrity(celebrityCandidate, numberOfPeople):
RETURN celebrityCandidate
ENDIF
RETURN -1
ENDFUNCTION
FUNCTION isCelebrity(celebrityCandidate, numberOfPeople):
FOR i IN RANGE(numberOfPeople):
IF (i==celebrityCandidate):
continue // skip checking self
ENDIF
IF (knows(i, celebrityCandidate) OR NOT knows(celebrityCandidate, i)):
RETURN false
ENDFOR
RETURN TRUE
ENDFUNCTION
