LeetCode · #4

Median of Two Sorted Arrays Solution

Given two sorted arrays nums1 and nums2, return the median of the combined sorted array in O(log(m+n)) time.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #4

🏗️

Pattern

Binary Search — partition on smaller array

Given two sorted arrays nums1 (size m) and nums2 (size n), return the median of the two sorted arrays. The overall run time complexity must be O(log(m+n)).

Example 1

 Input: nums1 = [1,3], nums2 = [2]
Output: 2.0 // Merged: [1,2,3] → median = 2 

Example 2

 Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5 // Merged: [1,2,3,4] → median = (2+3)/2 = 2.5 

Constraints

 • nums1.length == m, nums2.length == n • 0 ≤ m, n ≤ 1000 • 1 ≤ m + n ≤ 2000 • -10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶ 

Section Two · Approach 1

Merge & Find — O(m + n)

Merge both arrays into one sorted array (like merge sort's merge step), then pick the middle element(s). Correct but O(m+n) time and space.

Problem: O(m+n) violates the O(log(m+n)) requirement. We don't need the full merged array — we just need to find the correct partition point using binary search on the smaller array.

Java — Merge

 class Solution {
public double findMedianSortedArrays(int[] a, int[] b) {
int[] merged = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
            merged[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < a.length) merged[k++] = a[i++];
while (j < b.length) merged[k++] = b[j++];
int n = merged.length;
return n % 2 == 1 ? merged[n/2] : (merged[n/2-1] + merged[n/2]) / 2.0;
    }
}

Python — Merge

 class Solution:
def findMedianSortedArrays(self, a: list[int], b: list[int]) -> float:
        merged = sorted(a + b)
        n = len(merged)
if n % 2: return merged[n // 2]
return (merged[n // 2 - 1] + merged[n // 2]) / 2 

Metric	Value
Time	O(m + n)
Space	O(m + n)

Section Three · Approach 2

Binary Search on Partition — O(log min(m, n))

The median divides the combined array into two equal halves. We binary search on the smaller array to find how many elements it contributes to the left half. The remaining come from the larger array. A valid partition satisfies: maxLeft1 ≤ minRight2 and maxLeft2 ≤ minRight1.

💡 Mental model: Imagine cutting two decks of sorted cards so that when you combine the left portions, you have exactly half the total cards — and every card on the left is ≤ every card on the right. You slide the cut point on the smaller deck; the cut on the larger deck adjusts automatically (it takes whatever is needed to make up half). Binary search finds the correct cut in O(log n) tries.

Algorithm

Step 1: Ensure nums1 is the smaller array (swap if needed).
Step 2: Binary search i on nums1: left = 0, right = m. Compute j = half - i where half = (m+n+1)/2.
Step 3: Compute four boundary values: maxLeft1 = nums1[i-1], minRight1 = nums1[i], maxLeft2 = nums2[j-1], minRight2 = nums2[j].
Step 4: If maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1 → valid partition. Compute median.
Step 5: If maxLeft1 > minRight2 → too far right on nums1 → right = i - 1.
Step 6: Else → too far left → left = i + 1.

🎯 Key insight — half = (m+n+1)/2:

We want the left half to contain half elements.
Using (m+n+1)/2 (ceiling division) means for odd totals the left half has one extra element and the median is max(maxLeft1, maxLeft2).
For even totals, it's the average of the max of left and min of right.

Handling boundaries:

When i=0 or j=0, use -∞ for maxLeft (no elements on left from that array).
When i=m or j=n, use +∞ for minRight (no elements on right).
In code: Integer.MIN_VALUE and Integer.MAX_VALUE.

Section Four · Trace

Visual Walkthrough

Trace: nums1 = [1, 3], nums2 = [2, 4], half = (2+2+1)/2 = 2:

Partition search — split into equal left/right halves

Section Five · Implementation

Code — Java & Python

Java — Binary Search on Partition

 class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int left = 0, right = m;
int half = (m + n + 1) / 2;
while (left <= right) {
int i = left + (right - left) / 2; // partition in nums1 int j = half - i; // partition in nums2 int maxLeft1  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int maxLeft2  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// Valid partition if ((m + n) % 2 == 1)
return Math.max(maxLeft1, maxLeft2);
return (Math.max(maxLeft1, maxLeft2)
                      + Math.min(minRight1, minRight2)) / 2.0;
            } else if (maxLeft1 > minRight2) {
                right = i - 1; // too far right in nums1
} else {
                left = i + 1; // too far left in nums1
}
        }
return 0.0; // unreachable
}
}

Python — Binary Search on Partition

 class Solution:
def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        left, right = 0, m
        half = (m + n + 1) // 2 while left <= right:
            i = (left + right) // 2
j = half - i

            max_l1 = float('-inf') if i == 0 else nums1[i - 1]
            min_r1 = float('inf') if i == m else nums1[i]
            max_l2 = float('-inf') if j == 0 else nums2[j - 1]
            min_r2 = float('inf') if j == n else nums2[j]
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return max(max_l1, max_l2)
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2 elif max_l1 > min_r2:
                right = i - 1 else:
                left = i + 1 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Merge	O(m + n)	O(m + n)	Simple but linear
Two-pointer count	O(m + n)	O(1)	No extra array but still linear
Binary Partition ← optimal	O(log min(m,n))	O(1)	Search on the smaller array's partition

Why search the smaller array?:

Binary searching on the smaller array (m ≤ n) gives O(log m).
The partition in the larger array is determined automatically: j = half - i.
This guarantees j ≥ 0 because we ensured m ≤ n.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
One empty	`[], [1,2,3]`	i always 0, j = half. Median from nums2 alone.
Disjoint	`[1,2], [3,4]`	All of nums1 on left, partition cleanly at boundary.
Interleaved	`[1,3], [2,4]`	Elements alternate — partition must carefully balance.
Odd total	`[1,3], [2]`	Merged [1,2,3] → median = max of left half = 2.
Equal elements	`[1,1], [1,1]`	All same → partition anywhere works. Median = 1.0.

⚠ Common Mistake: Not swapping to ensure nums1 is smaller. If you binary search on the larger array, j = half - i can become negative (when i is too large), causing an index-out-of-bounds error. Always ensure m ≤ n before the search.

← Back to Binary Search problems

LearningTree

LC 4 · Median of Two Sorted Arrays — Solution & Explanation | DSA Guide