Median of Two Sorted Arrays hard

Problem Statement

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5

Steps

The optimal approach to solve this problem efficiently involves a binary search strategy. We don't explicitly merge the arrays. Instead, we use binary search to find a partition point in one array such that the elements to the left and right of the partition satisfy the median condition.

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 the smaller array: Swap arrays if nums1 is longer than nums2 to optimize the binary search.
3. Binary search on nums1: Perform a binary search on nums1 to find a partition partitionX such that:
   • partitionX elements from nums1 are less than or equal to the median.
   • The remaining nums1.length - partitionX elements from nums1 are greater than or equal to the median.
4. Determine partitionY (in nums2): The partition in nums2 (partitionY) is determined based on the total number of elements and partitionX. The formula is derived from the condition that the number of elements to the left of both partitions should be equal to the number of elements to the right.
5. Check the partition validity: Verify if the maximum element on the left (maxLeft) is less than or equal to the minimum element on the right (minRight). If this condition holds true, the median is found.
6. Adjust the binary search: If maxLeft > minRight, we need to adjust partitionX (move it left or right based on which side is larger).
7. Calculate the median: Once the correct partitions are found, calculate the median. If the total number of elements is even, it's the average of maxLeft and minRight. Otherwise, it's maxLeft (or minRight, they'll be equal).

Explanation

The core idea is to efficiently find the middle element(s) without explicitly merging the arrays. The binary search approach ensures a logarithmic time complexity. By partitioning the arrays smartly, we guarantee that the left partition always contains the smaller half of the combined array and the right partition contains the larger half, allowing us to directly compute the median.

Code

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    // Handle trivial cases
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]; // Ensure nums1 is the smaller array
    }

    const m = nums1.length;
    const n = nums2.length;
    let low = 0, high = m;

    while (low <= high) {
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = Math.floor((m + n + 1) / 2) - partitionX;

        const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        const minRightX = partitionX === m ? Infinity : nums1[partitionX];
        const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        const minRightY = partitionY === n ? Infinity : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            const maxLeft = Math.max(maxLeftX, maxLeftY);
            const minRight = Math.min(minRightX, minRightY);
            return (m + n) % 2 === 0 ? (maxLeft + minRight) / 2 : maxLeft;
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    throw new Error("Should not reach here"); // Should never reach this line if the input is valid
};

Complexity

• Time Complexity: O(log(min(m, n))), due to the binary search on the smaller array.
• Space Complexity: O(1), constant extra space is used. The algorithm operates in-place.