Median of Two Sorted Arrays

Description

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return 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.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

---

Brute Force Approach: Merge and Find Median

Intuition

Merge both sorted arrays into a single sorted array of size $m+n$ using the two-pointer merging technique. Once merged, return the middle element if the total length is odd, or the average of the two middle elements if even.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
 
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
 
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
 
        int total = m + n;
        if (total % 2 == 1) {
            return merged[total / 2];
        } else {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        }
    }
}
 

Complexity

• Time Complexity: $O(m+n)$ — Merges all elements into a new array.
• Space Complexity: $O(m+n)$ — Requires extra memory for the merged array.

---

Better Approach: Two Pointers ($O(1)$ Space)

Intuition

We don’t need to store the entire merged array. We only need the element(s) at index (m + n) / 2 and (m + n) / 2 - 1. Simulate the two-pointer merge process using a counter and keep track of only the last two seen elements.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int targetIdx2 = total / 2;
 
        int i = 0, j = 0, count = 0;
        int val1 = 0, val2 = 0;
 
        while (count <= targetIdx2) {
            val1 = val2;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                val2 = nums1[i++];
            } else {
                val2 = nums2[j++];
            }
            count++;
        }
 
        if (total % 2 == 1) {
            return val2;
        } else {
            return (val1 + val2) / 2.0;
        }
    }
}
 

Complexity

• Time Complexity: $O(m+n)$ — Traverses up to half of the combined elements.
• Space Complexity: $O(1)$ — Uses constant auxiliary memory.

---

Most Optimized Solution: Binary Search on Partition

Intuition

Instead of merging, partition both arrays into two equal-sized left and right halves such that:

1. Total elements in left half $=\lfloor (m+n+1)/2\rfloor$.
2. Every element in the left half is $\le$ every element in the right half.

Binary search on the smaller array (nums1) to find the partition cut point partition1:

• partition1 elements taken from nums1
• partition2 = (m + n + 1) / 2 - partition1 elements taken from nums2

Check the boundary conditions:

• maxLeft1 <= minRight2 AND maxLeft2 <= minRight1
• If maxLeft1 > minRight2, we took too many elements from nums1 $\to$ move left (high = partition1 - 1).
• Otherwise, move right (low = partition1 + 1).

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to minimize binary search steps
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
 
        int m = nums1.length;
        int n = nums2.length;
        int low = 0, high = m;
 
        while (low <= high) {
            int partition1 = low + (high - low) / 2;
            int partition2 = (m + n + 1) / 2 - partition1;
 
            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
 
            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
 
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                high = partition1 - 1; // Move left
            } else {
                low = partition1 + 1;  // Move right
            }
        }
 
        return 0.0;
    }
}
 

Complexity

• Time Complexity: $O(\log (\min (m,n)))$ — Binary search runs on the smaller array size.
• Space Complexity: $O(1)$ — Constant memory.

---

Easy Memory Rule

“Partition smaller array into left and right. Valid partition requires l1 <= r2 and l2 <= r1. Binary search adjusts partition until valid.”

1. The Core Idea: Why Partitioning Works

By definition, the median splits a sorted array into two equal halves:

1. Left Half: Contains the smaller half of all numbers.
2. Right Half: Contains the larger half of all numbers.
3. Every single number in the Left Half $\le$ every single number in the Right Half.

Since we have two sorted arrays instead of one, we slice both arrays at specific cut points so that:

• The total count of elements in Left1 + Left2 equals half of the total combined elements.
• Every number in Left1 + Left2 is smaller than or equal to every number in Right1 + Right2.

---

2. Why partition2 = (m + n + 1) / 2 - partition1?

• Total size of left half: We need the left side to hold exactly half of the total combined elements, which is (m + n + 1) / 2.

• Why the + 1?: It handles both even and odd total lengths using standard integer division:

• Even total (e.g., 6 elements): (6 + 1) / 2 = 3 elements in the left half.

• Odd total (e.g., 5 elements): (5 + 1) / 2 = 3 elements in the left half. (The left half gets 1 extra element, meaning the median is simply the largest value in the left half).

• The Formula: If binary search decides to pick partition1 elements from nums1 for the left half, then nums2 must supply the remaining amount to reach the target size:

$\text{partition2}=\frac{m+n+1}{2}-\text{partition1}$

---

3. Purpose of the Boundary Variables

When we cut nums1 at partition1 and nums2 at partition2, each array gets split into two pieces around the cut:

nums1: [ ... maxLeft1 ] | [ minRight1 ... ]
nums2: [ ... maxLeft2 ] | [ minRight2 ... ]
 

• maxLeft1: The largest element on the left side of nums1 (nums1[partition1 - 1]).
• minRight1: The smallest element on the right side of nums1 (nums1[partition1]).
• maxLeft2: The largest element on the left side of nums2 (nums2[partition2 - 1]).
• minRight2: The smallest element on the right side of nums2 (nums2[partition2]).

Why use Integer.MIN_VALUE and Integer.MAX_VALUE?

If a partition cut is at index 0 (taking 0 elements from an array), there is no left element, so we assign Integer.MIN_VALUE. If a cut is at the end (taking all elements), there is no right element, so we assign Integer.MAX_VALUE. This prevents out-of-bounds errors during comparisons.

---

4. Purpose of the if-else Conditions

Because nums1 and nums2 are already sorted individually, we already know maxLeft1 <= minRight1 and maxLeft2 <= minRight2.

To verify our combined left half is completely valid, we only need to cross-check the boundary diagonals:

Condition 1: Perfect Partition Found

if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
 

• Meaning: All left elements are smaller than all right elements. The cut is correct!
• Calculate Median:
• If total length is odd: Median is Math.max(maxLeft1, maxLeft2).
• If total length is even: Median is the average of Math.max(maxLeft1, maxLeft2) and Math.min(minRight1, minRight2).

Condition 2: Took Too Many Elements From nums1

else if (maxLeft1 > minRight2)
 

• Meaning: maxLeft1 is too big to belong in the left half. We need to take fewer elements from nums1.
• Action: Move binary search left (high = partition1 - 1).

Condition 3: Took Too Few Elements From nums1

else // (maxLeft2 > minRight1)
 

• Meaning: maxLeft2 is too big, which means partition2 was forced to take too many elements from nums2. We need to take more elements from nums1.
• Action: Move binary search right (low = partition1 + 1).