Python solution, beats 100%


  • 0
    P

    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
    

Log in to reply
 

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