My 150 ms python solution : What's the complexity though ?

  • 0
    class Solution:
        # @return a float
        def findMedianSortedArrays(self, A, B):
            A = sorted(A + B )
            if len(A) > 2:
                if len(A)%2 != 0 :
                    return A[(len(A)/2)]
                return float(A[(len(A)/2)] + A[(len(A)/2)-1])/2
            elif len(A) ==2 :
                return float(A[0] + A[1])/2
            elif len(A) == 1:
                return A[0]
            elif len(A) == 0:
                return None 

    Step 1 : Merged the two arrays and sorted the new list

    Step 2 : Return Median based on the length of the new list

  • 4

    Looking at the the first line in the function A = sorted(A + B), you should realize that your program is, to say the least, O((m+n)log(m + n)).

    Most interviewers won't be satisfied by this solution. You should at least bring the complexity to O(m+n). But ultimately, you are expected to reach O(log(m+n)) or better yet O(log(min(m+n))). The O(m+n) solution is simple, but the O(log(m+n)) is very hard to implement. Give it a try!

Log in to reply

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