Median of Two Sorted Arrays hard

Problem Statement

Find the median of two sorted arrays. The overall run time complexity should be O(log (m+n)), where m and n are the lengths of the two sorted arrays.

Example 1

nums1 = [1, 3], nums2 = [2]

The median is 2.0

Example 2

nums1 = [1, 2], nums2 = [3, 4]

The median is 2.5

Steps

The optimal solution leverages the concept of binary search. The core idea is to find a partition point in the two arrays such that the left half of the combined array is smaller than the right half. This partition should ideally split the elements into two equal-sized halves (or with a difference of at most 1 if the total number of elements is odd).

Here's a breakdown of the steps:

1. Handle Trivial Cases: If one array is empty, the median is simply the median of the other array.
2. Ensure nums1 is shorter: Swap the arrays if nums1 is longer than nums2 to optimize the binary search.
3. Binary Search on nums1: We perform binary search on the smaller array (nums1). The partition point in nums1 determines a corresponding partition point in nums2 to ensure the condition of equal (or almost equal) sizes for the left and right halves of the combined array.
4. Calculate Partition Points: Let partitionX be the partition point in nums1, and partitionY be the partition point in nums2. These are calculated based on the lengths of the arrays and partitionX.
5. Check Partition Validity: We verify if the condition max(nums1[partitionX-1], nums2[partitionY-1]) <= min(nums1[partitionX], nums2[partitionY]) holds true. This checks if the left half is entirely less than or equal to the right half.
6. Adjust Partition: Based on the validation, we adjust the partitionX using binary search (moving it left or right) until the valid partition is found.
7. Calculate Median: Once the valid partition is found, we calculate the median based on whether the total number of elements is even or odd.

Explanation

The binary search efficiently narrows down the possible partition points. By ensuring the left half is less than or equal to the right half, we guarantee that the median is correctly determined. The logarithmic time complexity comes from the efficient search in the smaller array.

Code

def findMedianSortedArrays(nums1, nums2):
    """
    Finds the median of two sorted arrays.

    Args:
        nums1: The first sorted array.
        nums2: The second sorted array.

    Returns:
        The median of the combined arrays.
    """
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A  # Ensure A is the shorter array

    m, n = len(A), len(B)
    low, high = 0, m

    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (m + n + 1) // 2 - partitionX

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

        maxLeftY = B[partitionY - 1] if partitionY > 0 else float('-inf')
        minRightY = B[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.0
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

    return 0 # Should never reach here if input is valid

Complexity

• Time Complexity: O(log(min(m, n))) due to the binary search on the shorter array.
• Space Complexity: O(1). The algorithm uses constant extra space.