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 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.
i does not know anyone on the LHS of i
(b) All elements on the RHS know
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