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

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Steps

The core idea is to use binary search to find a partition point in the smaller array that allows us to efficiently find the median. Here's a breakdown of the steps:

1. Ensure nums1 is the smaller array: Swap nums1 and nums2 if nums1 is longer than nums2. This simplifies the logic.

2. Binary Search: Perform a binary search on nums1. The goal is to find a partition partitionX in nums1 such that the number of elements to the left of partitionX in nums1 plus the number of elements to the left of a corresponding partition partitionY in nums2 equals (m+n)/2.

3. Calculate partitionY: partitionY is determined by the equation: partitionY = (m + n + 1) / 2 - partitionX (The +1 handles cases with an odd total number of elements).

4. Find maxLeft and minRight: After finding partitionX and partitionY, identify maxLeft (the maximum of the left partitions) and minRight (the minimum of the right partitions). These are crucial for determining the median.

5. Calculate the Median: If m + n is even, the median is the average of maxLeft and minRight. Otherwise, it's just maxLeft (or minRight, as they'll be equal).

Explanation

The binary search cleverly avoids explicitly merging the arrays. By carefully choosing the partition points, we can find the median using just the partition values. The correctness relies on the fact that we have two sorted arrays – the partitioning ensures we've considered elements from both arrays that would be present in the sorted merged array.

Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        // Ensure nums1 is the smaller array
        if (m > n) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            int tempLen = m;
            m = n;
            n = tempLen;
        }

        int low = 0, high = m;
        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;

            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((m + n) % 2 == 0) {
                    return (double) (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                } else {
                    return (double) Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        throw new IllegalArgumentException("Arrays are not sorted."); // Should never reach here if inputs are valid.
    }
}

Complexity

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