Finding the Median of Two Sorted Arrays

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

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

Brute Force Solution

The most straightforward approach is to merge the two sorted arrays into a single sorted array and then find the median.

1. Merge nums1 and nums2 into a new array merged. This takes O(m+n) time.
2. Sort the merged array. This takes O((m+n)log(m+n)) time.
3. If the length of merged is odd, the median is the middle element.
4. If the length of merged is even, the median is the average of the two middle elements.

Code (Python)

def findMedianSortedArrays_brute_force(nums1, nums2):
    merged = nums1 + nums2
    merged.sort()
    n = len(merged)
    if n % 2 == 0:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2
    else:
        return float(merged[n // 2])

Time Complexity

O((m+n)log(m+n)) due to sorting the merged array.

Space Complexity

O(m+n) because we create a new merged array.

Optimal Solution

To achieve O(log (m+n)) runtime complexity, we can use a binary search approach. The key idea is to find the correct partition in both arrays such that:

1. All elements to the left of the partitions are smaller than or equal to all elements to the right of the partitions.
2. The total number of elements to the left of the partitions is equal to (m+n+1)/2. This ensures we are at the median.

Steps:

1. Ensure nums1 is the smaller array. If not, swap them.
2. Initialize low = 0 and high = m (length of nums1).
3. Perform binary search:
   • Calculate partitionX = (low + high) // 2
   • Calculate partitionY = (m + n + 1) // 2 - partitionX
   • Find maxLeftX, minRightX, maxLeftY, minRightY (edge cases consider float('-inf') and float('inf'))
   • If maxLeftX <= minRightY and maxLeftY <= minRightX, we found the correct partitions.
     • If (m+n) is even, return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
     • If (m+n) is odd, return max(maxLeftX, maxLeftY)
   • If maxLeftX > minRightY, move high = partitionX - 1
   • Else, move low = partitionX + 1

Code (Python)

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    low, high = 0, m
    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (m + n + 1) // 2 - partitionX

        maxLeftX = nums1[partitionX - 1] if partitionX > 0 else float('-inf')
        minRightX = nums1[partitionX] if partitionX < m else float('inf')

        maxLeftY = nums2[partitionY - 1] if partitionY > 0 else float('-inf')
        minRightY = nums2[partitionY] if partitionY < n else float('inf')

        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (m + n) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            else:
                return float(max(maxLeftX, maxLeftY))
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1
    return -1 # Should not happen, but included for completeness

Time Complexity

O(log(min(m, n))) because we perform binary search on the smaller array.

Space Complexity

O(1) because we do not use any extra space.

Edge Cases

• Empty arrays: The code handles cases where one or both arrays are empty.
• Arrays of different lengths: The code correctly handles arrays of different lengths by performing binary search on the smaller array.
• Integer overflow: The intermediate sum of two numbers can cause an overflow if the sum is outside the range of integers. This specific median problem will not cause integer overflows, because the numbers are floats.