# Python solution, beats 100%

• One obvious solution is to check every pair in O(n^2), but this problem can be solved in O(n) time. One important idea to appreciate the fact that at most one celebrity can exist among the n people. If we can eliminate all non-celebrities in one pass (Step 1) and get a potential celebrity then the second pass (Step 2) would be to check if the potential celebrity is really a celebrity. Here are what Step 1 and Step 2 would roughly look like:

Step 1: We find an i such that:
(a) All elements to the left hand side (LHS) of `i` know `i`
(b) `i` does not know any element on the right hand side (RHS) of i.

Step 2: First pass/step will eliminate all non-celebrities and leave us with a potential celebrity, but we still have to check if this potential celebrity `i` satisfies the remaining (complementary) conditions we did not check in step 1 i.e.
(a) `i` does not know anyone on the LHS of i
(b) All elements on the RHS know `i`

Here is the code (beats 100% Python solutions), that illustrates Step 1 and Step 2 in more detail.

``````    def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return -1
if n == 1:
return 0

i = 0
j = 1

# Step 1: O(n) Eliminating non-celebrities and finding one potential celebrity, i.
while True:
if knows(i, j):
i = j
j += 1
if j == n:
break

# Step 2: O(n) Check that the potential celebrity i is really a celebrity
people = range(n)
lhs = people[:i]
rhs = people[i+1:]

for p in lhs:
if knows(i, p):
return -1

for p in rhs:
if not knows(p, i):
return -1

return i
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.