LeetCode Solutions Blog

Median of Two Sorted Arrays

Difficulty: Hard

Problem Description

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

Key Insights

The median is the middle value in a sorted list. If the total number of elements is odd, it is the middle element; if even, it is the average of the two middle elements.
Merging the arrays directly would take O(m+n) time, but we need an O(log(m+n)) solution.
We can use a binary search approach to partition the arrays while ensuring that all elements on the left partition are less than or equal to all elements on the right partition.

Space and Time Complexity

Time Complexity: O(log(min(m, n)))
Space Complexity: O(1)

Solution

We can use the binary search algorithm to find the correct partition between the two arrays. The idea is to maintain two partitions, one from each array, such that all elements in the left partition are less than or equal to those in the right partition. The median can then be calculated based on the max of the left partitions and the min of the right partitions.

Code Solutions

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    total = m + n
    half = total // 2
    
    left, right = 0, m
    
    while left <= right:
        partition1 = (left + right) // 2
        partition2 = half - partition1
        
        maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = float('inf') if partition1 == m else nums1[partition1]
        
        maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = float('inf') if partition2 == n else nums2[partition2]
        
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            # We have partitioned the arrays correctly
            if total % 2 == 0:
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
            else:
                return max(maxLeft1, maxLeft2)
        elif maxLeft1 > minRight2:
            right = partition1 - 1
        else:
            left = partition1 + 1