34.Median of Two Sorted Arrays

HardBinary Search · 7/7

Problem

Given two sorted arrays nums1 (size m) and nums2 (size n), return the median of the combined multiset of their elements.

The overall run time complexity should be O(log(m + n)). The median is the middle value of the merged sorted order; if the total count is even, it is the average of the two middle values.

Examples

Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.00000
Explanation: merged = [1, 2, 3]; the middle element is 2.

Input:  nums1 = [1, 2], nums2 = [3, 4]
Output: 2.50000
Explanation: merged = [1, 2, 3, 4]; median = (2 + 3) / 2 = 2.5.

Input:  nums1 = [], nums2 = [5]
Output: 5.00000

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

💡 Key Insight

The median splits the merged array into a left half and a right half of equal size (left gets the extra element when the total is odd). If we take i elements from nums1 and j = half - i from nums2 for the left half, the split is correct exactly when nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]. Choosing i determines j, and the conditions are monotonic in i, so we can binary-search i over the shorter array — O(log(min(m, n))) without merging anything.

Brute Force (Merge Into New Array)

TimeO(m + n)SpaceO(m + n)

Intuition

Do exactly what the definition says: merge both sorted arrays into one sorted array (the merge step of merge sort), then read off the middle element(s).

Algorithm

Create merged of size m + n; merge with two pointers, always copying the smaller head.
Copy any leftovers.
If total is odd return merged[total / 2]; else return the average of merged[total/2 - 1] and merged[total/2].

Visualization

nums1 = [1, 2], nums2 = [3, 4]
merged = [1, 2, 3, 4]
             ^  ^
     middles 2 and 3 → (2 + 3) / 2 = 2.5

Code

java

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) {
            merged[k++] = (nums1[i] <= nums2[j]) ? nums1[i++] : 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];
        }
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
}

Complexity

Time: O(m + n) — every element is copied once.
Space: O(m + n) — the merged array.

Two Pointers Without Extra Array

TimeO(m + n)SpaceO(1).

Intuition

We never need the whole merged array — only the elements at positions total/2 - 1 and total/2. Simulate the merge, advancing one pointer per step, and stop after total/2 + 1 steps while remembering the previous and current values.

Algorithm

i = j = 0, prev = cur = 0.
Repeat total / 2 + 1 times:
- prev = cur.
- If nums1 still has elements and (nums2 is exhausted or nums1[i] <= nums2[j]), cur = nums1[i++]; else cur = nums2[j++].
If total is odd return cur; else return (prev + cur) / 2.0.

Dry Run

nums1 = [1, 3], nums2 = [2]   total = 3 → 2 steps
step 0: 1 ≤ 2 → cur = 1 (i=1)
step 1: 3 > 2 → cur = 2 (j=1)
odd total → return 2

Code

java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int i = 0, j = 0;
        int prev = 0, cur = 0;
        for (int step = 0; step <= total / 2; step++) {
            prev = cur;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                cur = nums1[i++];
            } else {
                cur = nums2[j++];
            }
        }
        if (total % 2 == 1) {
            return cur;
        }
        return (prev + cur) / 2.0; // two middle values
    }
}

Complexity

Time: O(m + n) — about half of the elements are visited.
Space: O(1).

Binary Search on PartitionOptimal

TimeO(log(min(m, n)))SpaceO(1)

Intuition

Let A be the shorter array and B the longer one, half = (m + n + 1) / 2. Pick a cut i in A (taking A[0..i-1] into the left half) which forces the cut j = half - i in B. Name the four border values:

L1 = A[i-1], R1 = A[i], L2 = B[j-1], R2 = B[j] (use -∞ / +∞ when a side is empty).

The partition is valid when L1 <= R2 and L2 <= R1. If L1 > R2, we took too many from A → move i left. If L2 > R1, we took too few → move i right. Once valid, the median is max(L1, L2) (odd total) or the average of max(L1, L2) and min(R1, R2) (even total).

Algorithm

If nums1 is longer, swap so A is the shorter array.
lo = 0, hi = m, half = (m + n + 1) / 2.
While lo <= hi:
- i = (lo + hi) / 2, j = half - i.
- Compute L1, R1, L2, R2 with sentinels.
- If L1 <= R2 && L2 <= R1 → return the median as above.
- Else if L1 > R2 → hi = i - 1; else lo = i + 1.

Dry Run

flowchart TD
    A["A = [1,2], B = [3,4]<br/>m=2, n=2, half=2, lo=0, hi=2"] --> B["i=1, j=1<br/>L1=1, R1=2, L2=3, R2=4"]
    B --> C{"L2=3 ≤ R1=2?"}
    C -->|"no: too few from A"| D["lo=2"]
    D --> E["i=2, j=0<br/>L1=2, R1=+inf, L2=-inf, R2=3"]
    E --> F{"L1 ≤ R2 and L2 ≤ R1?"}
    F -->|"yes"| G["even total:<br/>(max(2,-inf) + min(+inf,3)) / 2"]
    G --> H["return 2.5"]

left half         | right half
A: 1 2            |  (empty)
B: (empty)        |  3 4
max(left) = 2       min(right) = 3   → median = 2.5

Code

java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // binary search over the shorter array so j = half - i stays in range
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length, n = nums2.length;
        int half = (m + n + 1) / 2; // left half gets the extra element when total is odd
        int lo = 0, hi = m;

        while (lo <= hi) {
            int i = lo + (hi - lo) / 2; // elements taken from nums1
            int j = half - i;           // elements taken from nums2

            int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (left1 <= right2 && left2 <= right1) {
                // correct partition found
                if ((m + n) % 2 == 1) {
                    return Math.max(left1, left2);
                }
                return ((double) Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
            } else if (left1 > right2) {
                hi = i - 1; // took too many from nums1
            } else {
                lo = i + 1; // took too few from nums1
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted");
    }
}

Complexity

Time: O(log(min(m, n))) — binary search over the shorter array only.
Space: O(1) — the swap is a single extra call frame.

Complexity Comparison

Approach	Time	Space
Merge Into New Array	O(m + n)	O(m + n)
Two Pointers	O(m + n)	O(1)
Binary Search on Partition	O(log(min(m, n)))	O(1)

Common Pitfalls

Binary-searching the longer array — then j = half - i can become negative or exceed n, causing index errors.
Forgetting the sentinels: when i == 0, i == m, j == 0 or j == n one side is empty and must act as -∞ / +∞.
Integer division for the even case: (a + b) / 2 truncates; divide by 2.0 (and cast to double before adding to avoid overflow).
Using half = (m + n) / 2 with "median = max(left)" for odd totals — the extra element then lands on the right side and you would need min(R1, R2) instead. Pick one convention and stay consistent.
Handling an empty array: the optimal code covers m = 0 naturally (i is always 0).