LeetCode #4: Median of Two Sorted Arrays

Problem Description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution:

• Method 1: merge two array and return the median

  • Time complexity: O(m+n)
  • Space complexity: O(m+n)

• Method 2: divide and conquer

  • Time complexity: O(log(m+n))
  • Space complexity: O(1)

class Solution:
    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':
        method = 'divide_conquer'

        if method == 'merge':
            total = self.merge(nums1, nums2)
            n = len(total) 
            if n % 2 == 1:
                return float(total[int(n//2)])
            else:
                return (total[int(n/2)-1] + total[int(n/2)]) / 2.0

        if method == 'divide_conquer':
            n = len(nums1) + len(nums2)
            if n % 2 == 1:
                return float(self.diviconq(nums1, nums2, int(n/2)))
            else:
                return (self.diviconq(nums1, nums2, int(n/2)-1) + self.diviconq(nums1, nums2, int(n/2))) / 2.0


    def merge(self, array1, array2):
        n1 = len(array1)
        n2 = len(array2)
        out = []
        i = 0; j = 0
        while i<n1 and j<n2:
            if array1[i] < array2[j]:
                out.append(array1[i])
                i+=1
            else:
                out.append(array2[j])
                j+=1
        if i>=n1-1: out = out + array2[j:]
        if j>=n2-1: out = out + array1[i:]
        return out 

    def diviconq(self, array1, array2, k):
        n1 = len(array1)
        n2 = len(array2)

        if n1 == 0:
            return array2[k]
        if n2 == 0:
            return array1[k]
        if n1==1 and n2==1:
            return sorted([array1[0], array2[0]])[k]

        im1 = int(n1/2)
        im2 = int(n2/2)

        if im1+im2 >= k:
            if array1[im1] > array2[im2]:
                return self.diviconq(array1[:im1], array2, k)
            else:
                return self.diviconq(array1, array2[:im2], k)
        else:
            if array1[im1] > array2[im2]:
                if im2==0:
                    return self.diviconq(array1[im1:], array2, k-im1)
                else:
                    return self.diviconq(array1, array2[im2:], k-im2)
            else:
                if im1==0:
                    return self.diviconq(array1, array2[im2:], k-im2)
                else:
                    return self.diviconq(array1[im1:], array2, k-im1)