LeetCode Solutions Blog

Median of Two Sorted Arrays

Number: 4

Difficulty: Hard

Paid? No

Problem Description

Given two sorted arrays nums1 and nums2 of sizes m and n respectively, find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Key Insights

The median divides the sorted array into two equal halves.
We can perform binary search on the smaller array to partition both arrays correctly.
We need to ensure that every element in the left partition is less than or equal to every element in the right partition.
Edge cases must be handled when partitions are at the boundaries of either array.

Space and Time Complexity

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

Solution

The solution uses a binary search technique on the smaller array. We define a partition index i for nums1 and compute the corresponding index j for nums2 such that i + j equals half of the total number of elements. The algorithm checks if the largest element on the left side of nums1 (if any) is less than or equal to the smallest element on the right side of nums2, and vice versa for nums2. If the condition holds, we have found the correct partition and compute the median. If not, adjust the binary search range until the correct partition is found. This partitioning strategy allows us to find the median in logarithmic time.

Code Solutions

# Function to find the median of two sorted arrays
def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array for faster binary search
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
        
    m, n = len(nums1), len(nums2)
    low, high = 0, m

    while low <= high:
        # Partition indexes for nums1 and nums2
        partition_nums1 = (low + high) // 2
        partition_nums2 = (m + n + 1) // 2 - partition_nums1
        
        # If partition is 0 then there are no elements on left side. Use -infinity for comparison.
        maxLeftNums1 = float('-inf') if partition_nums1 == 0 else nums1[partition_nums1 - 1]
        # If partition is length then there are no elements on right side. Use infinity for comparison.
        minRightNums1 = float('inf') if partition_nums1 == m else nums1[partition_nums1]
        
        # Similarly for nums2
        maxLeftNums2 = float('-inf') if partition_nums2 == 0 else nums2[partition_nums2 - 1]
        minRightNums2 = float('inf') if partition_nums2 == n else nums2[partition_nums2]
        
        # Check if we have found the correct partition
        if maxLeftNums1 <= minRightNums2 and maxLeftNums2 <= minRightNums1:
            # If total number of elements is even
            if (m + n) % 2 == 0:
                return (max(maxLeftNums1, maxLeftNums2) + min(minRightNums1, minRightNums2)) / 2.0
            else:
                return float(max(maxLeftNums1, maxLeftNums2))
        # If not, adjust binary search range
        elif maxLeftNums1 > minRightNums2:
            # Move partition in nums1 to left
            high = partition_nums1 - 1
        else:
            # Move partition in nums1 to right
            low = partition_nums1 + 1

# Example usage:
print(findMedianSortedArrays([1,3], [2]))  # Output: 2.0
print(findMedianSortedArrays([1,2], [3,4]))  # Output: 2.5