4. Median of Two Sorted Arrays

[goungoun]

Intuition

When I saw this question, i thought it should be easy or medium level. Why is it tagged as a hard question? It is because it says

The overall run time complexity should be O(log (m+n)).

Assumption

Two sorted arrays nums1 and nums2 are given.
To get a median, we have to have another sorted array, really?

Approach

I started from the easiest way and slowly improved the time and space complexity.

Built-in sort:
Merge two array into an array and simply called sort() that is a Tim sort with a time complexity O (n logn). And then find the mid index using its length is super easy.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)

        nums = nums1 + nums2 # S=O(n)
        nums.sort() # T=O(n*logn)
        
        mid, r = divmod(m+n, 2)

        if r != 0:
            return nums[mid]
        else:
            return (nums[mid-1] + nums[mid])/2

Merge Sorted list:
If built-in sort is not allowed, I can merge like this. With more codes, it decreases the complexity from O(n log n) to O(n). It is because nums1 and nums2 are already sorted. For the space complexity, it still requires another array list to store the result, so it is O(n).

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)

        nums = nums1 + nums2

        #nums.sort() # if not allowed
        i = 0
        j = 0
        nums = []

        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums.append(nums1[i])
                i += 1
            else:
                nums.append(nums2[j])
                j += 1
        
        if i < m:
            nums.extend(nums1[i:])
        
        if j < n:
            nums.extend(nums2[j:])
        
        mid, r = divmod(m+n, 2)

        if r != 0:
            return nums[mid]
        else:
            return (nums[mid-1] + nums[mid])/2

Two Pointer:
While merging the two arrays into the new array, it comes up my mind that why do I have to store all the sorted result? It is ok to removed as below. With that, the space complexity is improved from O(n) to O(1).

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:       
        m = len(nums1) if nums1 else 0
        n = len(nums2) if nums2 else 0

        mid, r = divmod(m+n, 2)

        i = 0
        j = 0
        
        curr = 0
        prev = 0

        while (i + j) <= mid:
            prev = curr
            if (0 <= i < m) and (0 <= j < n):
                if nums1[i] < nums2[j]:
                    curr = nums1[i]
                    i += 1       
                else:
                    curr = nums2[j]
                    j += 1
            elif 0 <= i < m:
                curr = nums1[i]
                i += 1 
            elif 0 <= j < n:
                curr = nums2[j]
                j += 1

        if r != 0:
            return curr
        else:
            return (curr + prev)/2

Solution

Time complexity should be O(log n)

Complexity

Built-in sort:

• Time complexity: O(n log n)
• Space complexity: O(n)

Merge Sorted list:

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

Two Pointer:

• Time complexity: O(n)
• Space complexity: O(1)

Binary Search:

• Time complexity: O(log n)
• Space complexity:

Conclusion