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
```