MANG Problem #2: Median of Two Sorted Arrays (Hard)

1. Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Constraint: The overall run time complexity should be $O(\log (m+n))$.

2. Approach: The "Partitioning" Strategy

graph LR
    subgraph "Array 1"
        L1[Left 1] | R1[Right 1]
    end
    subgraph "Array 2"
        L2[Left 2] | R2[Right 2]
    end
    
    Condition{L1 <= R2 && L2 <= R1?}
    Condition -- Yes --> Found[Median = max(L1,L2) + min(R1,R2) / 2]
    Condition -- No (L1 > R2) --> MoveLeft[Move Partition 1 Left]
    Condition -- No (L2 > R1) --> MoveRight[Move Partition 1 Right]

Finding the median is essentially finding a point that divides a combined set into two halves of equal length.

The Linear Way (O(m+n))

Merge both arrays into one and find the middle.

Why it fails: It violates the logarithmic time constraint.

The Logarithmic Way: Binary Search on Partition

We don't need to merge. We need to find a partition in nums1 (let's call it i) such that:

The left half of nums1 + the left half of nums2 equals the right half of both.
All elements in the combined left half are $\le$ all elements in the combined right half.

Condition:

L1 <= R2 and L2 <= R1

3. Java Implementation

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1); // Ensure nums1 is smaller
    }
    
    int m = nums1.length, n = nums2.length;
    int low = 0, high = m;
    
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (m + n + 1) / 2 - partitionX;
        
        int L1 = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int R1 = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
        
        int L2 = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int R2 = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];
        
        if (L1 <= R2 && L2 <= R1) {
            if ((m + n) % 2 == 0) {
                return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
            } else {
                return Math.max(L1, L2);
            }
        } else if (L1 > R2) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }
    throw new IllegalArgumentException();
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: We are binary searching for the index of the partition, not a value.
The Constraint: By performing binary search on the smaller array, we ensure the time complexity is $O(\log(\min(m, n)))$, which is even better than the requirement.
The Partition Balance: If L1 > R2, our partition in nums1 is too far to the right. We must move it left.
Dry Run:
- nums1 = [1, 3], nums2 = [2]
- m=2, n=1. nums1 is larger, swap.
- X = [2], Y = [1, 3].
- partitionX = 0, partitionY = 2.
- L1 = -∞, R1 = 2. L2 = 3, R2 = +∞.
- L2 > R1 (3 > 2). Move partitionX right.
- Result found.

5. Interview Discussion

Interviewer: "Why did you swap the arrays at the beginning?"
You: "To ensure we perform binary search on the smaller array, which guarantees the shortest possible runtime and prevents partitionY from being negative."
Interviewer: "How do you handle empty arrays?"
You: "The logic handles them using the MIN_VALUE and MAX_VALUE padding for partitions at the boundaries."