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 key to solving this problem efficiently is to avoid merging the two arrays completely. Instead, we can use a binary search approach to find the partition point that divides the merged array into two halves with equal (or nearly equal) sizes.

1. Handle edge cases: If one array is empty, return the median of the other array.
2. Determine the partition: We'll use binary search on the smaller array (nums1 in this case, assuming m <= n). The goal is to find a partition partitionX in nums1 such that nums1[partitionX - 1] <= nums2[partitionY] and nums2[partitionY - 1] <= nums1[partitionX] where partitionY = (m + n + 1) / 2 - partitionX.
3. Adjust partition: If the conditions in step 2 are not met, adjust partitionX using binary search until the conditions are satisfied.
4. Calculate median: Once the correct partition is found, the median can be calculated based on whether m + n is even or odd.

Explanation

The binary search approach focuses on finding the partition that splits the merged array into two halves. We search in the smaller array to minimize the search space. The condition nums1[partitionX - 1] <= nums2[partitionY] and nums2[partitionY - 1] <= nums1[partitionX] ensures that the elements to the left of the partition are less than or equal to the elements to the right, a necessary condition for finding the median.

The formula partitionY = (m + n + 1) / 2 - partitionX ensures that we are always considering partitions that result in equal or near-equal sized halves of the merged array. The + 1 handles cases with odd numbers of elements.

Code

using System;

public 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) {
            return FindMedianSortedArrays(nums2, nums1);
        }

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

            int maxLeftX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
            int minRightX = (partitionX == m) ? int.MaxValue : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
            int minRightY = (partitionY == n) ? int.MaxValue : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                int maxLeft = Math.Max(maxLeftX, maxLeftY);
                int minRight = Math.Min(minRightX, minRightY);

                return (m + n) % 2 == 0 ? (double)(maxLeft + minRight) / 2 : maxLeft;
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        throw new Exception("Should not reach here"); //Should never reach this point due to binary search properties
    }
}

Complexity

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