I've written a solution to the leetcode problem Median of Two Sorted arrays. The solution I anticipated coming up with initially was going to features some kind of binary search on both arrays based on the range of numbers (given that the question calls for a runtime of O(log (m+n))).

Along the way, I thought of another, simpler solution that featured averaging the largest number of both arrays (the last element of one of the arrays) and the smallest number of the two arrays (index 0 of one of the arrays). I also include a number of if statements to handle the possible different array lengths that could be passed in. I'm particularly interested in the approach of this solution since it would have a faster runtime than what was suggested.

This solution surprisingly passes 2056 / 2084 of the test cases. It fails, however, on the input arrays of [3],[-2,-1], which leads me to believe that the code will fail only when there exist negative numbers in either array. Is this the case, or is it just that the test cases used for the question aren't wide-ranging enough?

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        if len(nums1) == 0 and len(nums2) == 0:
            return None
        if len(nums1) == 0 and len(nums2) > 0:
            if len(nums2) == 1:
                return nums2[0]
            elif len(nums2) > 1 and len(nums2) % 2 == 1:
                lo,hi = 0,len(nums2)-1
                mid = (hi+lo)//2
                return nums2[mid]
            elif len(nums2) > 1 and len(nums2) % 2 == 0:
                lo,hi = 0,len(nums2)-1
                mid = (hi+lo)//2
                return (nums2[mid] + nums2[mid+1])/2

        if len(nums1) > 0 and len(nums2) == 0:
            if len(nums1) == 1:
                return nums1[0]
            elif len(nums1) > 1 and len(nums1) % 2 == 1:
                lo,hi = 0,len(nums1)-1
                mid = (hi+lo)//2
                return nums1[mid]
            elif len(nums1) > 1 and len(nums1) % 2 == 0:
                lo,hi = 0,len(nums1)-1
                mid = (hi+lo)//2
                return (nums1[mid] + nums1[mid+1])/2

        l1A,l2A,l1B,l2B = 0,0,len(nums1)-1,len(nums2)-1
        arrBeg = nums1[l1A] if nums1[l1A] <nums2[l2A] else nums2[l2A]
        arrEnd = nums1[l1B] if nums1[l1B] > nums2[l2B] else nums2[l2B]
        target = (arrEnd+arrBeg)/2
        return target

I believe the test cases are not generated randomly. Your code will fail on almost all cases if the cases are generated in a random way. For instance, if array A is [0, 10000], and array B contains an arbitrary number of elements with arbitrary values from (0, 10000) except 5000, your code will fail. It is not relevant if the test cases contain negative numbers or not.

| improve this answer | |
  • \$\begingroup\$ So you're essentially saying that if one of the arrays is a subset of the other, the code will fail? \$\endgroup\$ – loremIpsum1771 Oct 26 '18 at 14:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.