LeetCode Problem 4: Median of Two Sorted Arrays

Problem Statement

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)).

Understanding the Problem

Finding the median of two sorted arrays can be solved in O(m + n) time by merging the arrays and extracting the median. However, the problem requires an efficient O(log (m+n)) solution, which suggests using binary search.

Binary Search Approach

We use binary search on the smaller array to find the partition point such that both halves contain equal or nearly equal numbers of elements.

Steps:

1. Perform binary search on the smaller array.
2. Find a partition index i such that:
   • Left half of nums1[0:i] and nums2[0:j] contain floor((m+n)/2) elements.
   • Right half contains the remaining elements.
3. Ensure the partition is valid:
   • nums1[i - 1] <= nums2[j]
   • nums2[j - 1] <= nums1[i]
4. Compute the median based on partitioning.

Implementation

from typing import List

def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # Ensure nums1 is the smaller array

    x, y = len(nums1), len(nums2)
    low, high = 0, x

    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (x + y + 1) // 2 - partitionX

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

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

        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (x + y) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

    raise ValueError("Input arrays are not sorted properly")

Complexity Analysis

• Binary search runs in O(log min(m, n))
• Finding the median is O(1)
• Overall complexity: O(log(m + n))

Example Usage

nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.0

nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.5

Edge Cases Considered

• Arrays of different sizes
• Arrays containing negative numbers
• Arrays where one is empty
• Arrays where elements overlap

Conclusion

This approach efficiently finds the median using binary search rather than merging, achieving the required O(log(m + n)) complexity.