Median of Two Sorted Arrays

1. Problem & Core Objective

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array.

You must achieve O(log(m + n)) runtime.

nums1 = [1,3], nums2 = [2]       →  2.0      (merged: [1,2,3])
nums1 = [1,2], nums2 = [3,4]     →  2.5      (merged: [1,2,3,4], mean of 2 and 3)

Constraints: 0 <= m, n <= 1000 · 1 <= m + n <= 2000 · values in [-10^6, 10^6]

What's actually being tested: whether you can stop looking for a value and start looking for a cut. Every natural approach — merge, or step k times — is at least O(m + n). The logarithmic bound is only reachable by binary searching where to partition, which is a genuinely different framing.

This is the hardest problem in the section by a wide margin, and the one most worth over-preparing.

2. First-Principles Thought Process

What a median actually is

The median splits the combined data into two halves of equal size, where every element in the left half is ≤ every element in the right half.

• Odd total → the median is the largest element of the left half.
• Even total → the mean of the largest left and the smallest right.

Note this definition says nothing about sorting or merging. It only describes a split. That's the opening.

The reframe: search for the cut

Don't look for the median's value. Look for where to cut each array.

Cut nums1 after i elements and nums2 after j elements. Take those i + j elements as the left half. Two conditions make the cut correct:

1. Sizes match: i + j = half the total.
2. Ordering holds: everything on the left ≤ everything on the right.

Why there is only one variable

Condition 1 pins j once i is chosen:

j = half − i        where half = (m + n + 1) / 2

So the search space is just i, from 0 to m. One variable, binary searchable.

Checking condition 2 in O(1)

Within each array the ordering is already guaranteed — it's sorted. So only the cross-boundary comparisons can fail:

left1 ≤ right2      (the last taken from nums1 ≤ the first left in nums2)
left2 ≤ right1      (the last taken from nums2 ≤ the first left in nums1)

Two comparisons. That's the whole validity check.

Which way to move

• left1 > right2 → took too many from nums1 → decrease i.
• left2 > right1 → took too few from nums1 → increase i.

Monotonic in i, so binary search applies.

Four mechanics that make it work

1. Always binary search the shorter array. If m > n, swap them. Otherwise j = half − i can fall outside nums2's bounds — negative or past the end. The swap guarantees 0 <= j <= n.

2. Use ±∞ sentinels at the edges. When i == 0 there's no left1; treating it as −∞ makes the comparison pass automatically. Similarly right1 = +∞ when i == m. This removes every empty-side special case — and there are four of them.

3. half = (m + n + 1) / 2. The +1 puts the extra element on the left when the total is odd, so the odd answer is simply max(left1, left2) with no further branching.

4. Divide by 2.0. Integer division would silently truncate the even case.

3. Solution Paths

Approach 1 — Merge both arrays (brute force)

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;
}

The merge step of merge sort, then index into the middle.

• Time O(m + n) · Space O(m + n)

Counter-questions on this approach

⭐ "You build the entire merged array but read only one or two elements from it. What's wasted?"

Nearly everything. I need the middle one or two values, and I've computed and stored all m + n in sorted order. The median is defined by a split point, not by the full ordering — so I'm computing far more than the question asks.

That's the observation that leads to the answer: if the median is really about where the halves divide, I should be searching for the divide, not producing the sequence.

"Could you at least drop the space to O(1)?"

Yes — walk the two arrays with two pointers and count to the middle without storing anything, keeping only the last one or two values seen. That's Approach 2. It fixes the space but not the time, which is still O(m + n).

"Is O(m + n) actually too slow at m + n <= 2000?"

No — it would pass comfortably. But the problem states O(log(m+n)), and that requirement is the entire point of the question. It's a spec violation rather than a performance failure.

Approach 2 — Step to the middle without merging

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length, total = m + n;
    int i = 0, j = 0, prev = 0, cur = 0;

    for (int count = 0; count <= total / 2; count++) {
        prev = cur;
        if (i < m && (j >= n || nums1[i] <= nums2[j])) cur = nums1[i++];
        else                                          cur = nums2[j++];
    }
    return (total % 2 == 1) ? cur : (prev + cur) / 2.0;
}

Advance through the virtual merge, keeping only the last two values.

• Time O(m + n) · Space O(1)

Counter-questions on this approach

⭐ "This is O(1) space. What's still wrong with it?"

The time. I still walk half the elements one at a time — (m+n)/2 steps. I'm stepping toward the boundary when I could be jumping to it. The median's position is a boundary in an ordered space, and boundaries are what binary search locates in O(log n).

"The condition i < m && (j >= n || nums1[i] <= nums2[j]) is doing a lot. Walk me through it."

Three cases folded into one expression. Take from nums1 if: it still has elements and either nums2 is exhausted or nums1's next value is smaller. Otherwise take from nums2. The short-circuit ordering matters — i < m must come first, or nums1[i] would read out of bounds when nums1 is exhausted.

"Why track prev at all?"

For the even case, where the median averages the two middle values. The loop ends holding the upper middle in cur, and prev holds the one before it. Cheaper than re-scanning.

Approach 3 — Binary search the partition (optimal)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);  // search the SHORTER

    int m = nums1.length, n = nums2.length;
    int half = (m + n + 1) / 2;          // +1 puts the extra element on the LEFT when odd
    int lo = 0, hi = m;                  // how many to take from nums1

    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;      // taken from nums1
        int j = half - i;                // ...forces how many 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) {                  // valid partition
            if ((m + n) % 2 == 1) return Math.max(left1, left2);
            return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
        }
        if (left1 > right2) hi = i - 1;      // took too many from nums1
        else                lo = i + 1;      // took too few
    }
    throw new IllegalArgumentException("inputs are not sorted");
}

Trace — nums1 = [1,3], nums2 = [2]. After the swap nums1 = [2] (shorter), nums2 = [1,3]. So m=1, n=2, half = (3+1)/2 = 2.

Total is odd (3), so the answer is max(left1, left2) = max(2, 1) = 2.0 ✓

Trace — nums1 = [1,2], nums2 = [3,4]. m=n=2, half = (4+1)/2 = 2.

Even total, so (max(2,−∞) + min(∞,3)) / 2.0 = (2 + 3) / 2.0 = 2.5 ✓

Notice step 2 uses two sentinels — right1 and left2 — and the comparison still resolves cleanly. Without them that iteration would need explicit i == m and j == 0 branches.

• Time O(log(min(m, n))) · Space O(1)

Counter-questions on this approach

⭐ "Why must you binary search the shorter array? What breaks otherwise?"

j = half − i has to land inside nums2. If nums1 is the longer array, a large i drives j negative; a small i drives it past n. Either way you'd index out of bounds or compute a nonsense partition.

Searching the shorter array bounds i by m <= n, which guarantees 0 <= j <= n for every i in range. The one-line swap at the top is what makes the rest of the function safe — it isn't a micro-optimization.

⭐ "Explain the ±∞ sentinels. Why not handle the empty cases with if statements?"

Because there are four of them — i == 0, i == m, j == 0, j == n — and they can combine, so an explicit version needs a thicket of nested conditions.

The sentinels encode the meaning directly: if nothing was taken from the left of nums1, then "the largest element on that side" is −∞, which can never violate left1 <= right2. Likewise +∞ for an empty right side. Every boundary case then flows through the same two comparisons. In the second trace, three of the four were sentinels and the comparison still worked.

⭐ "Why (m + n + 1) / 2 rather than (m + n) / 2?"

The +1 puts the extra element on the left side when the total is odd. That makes the odd answer simply max(left1, left2) — the largest element of the left half — with no separate branch.

With (m+n)/2 the extra element would land on the right, and the odd case would need min(right1, right2) instead, plus different handling of which side is larger. The +1 is chosen to make the two cases share as much code as possible.

"Why is (m + n) % 2 computed from the originals rather than after the swap?"

The swap exchanges m and n but their sum is unchanged, so the parity is the same either way. Worth noting that I checked rather than assuming — a swap that altered the parity would silently break the even/odd branch.

"Why is the loop lo <= hi rather than lo < hi?"

Because i == lo == hi is a live candidate — the valid partition might be exactly there. This is an exact-match style search where the answer is found inside the loop and returned, not a boundary search that converges to lo. That's why it returns from within the loop rather than after it.

"Can this actually throw the exception at the end?"

Not for valid input. A valid partition always exists when both arrays are sorted — the validity predicate is monotonic in i, so the search is guaranteed to land on it. The throw documents the precondition and turns a silent wrong answer into a loud failure if the inputs aren't sorted.

"Could the sentinels cause an overflow in the even-case average?"

The average only runs on a valid partition, where Math.max(left1, left2) and Math.min(right1, right2) are both real array values — a sentinel can never win those. Values are bounded by 10^6, so the sum is at most 2 × 10^6. Safe. Worth verifying rather than assuming, since Integer.MAX_VALUE + Integer.MIN_VALUE appearing in an average would be a genuine bug.

Comparison

4. Why the Optimal Wins

Against merging. The merge produces a total ordering of m + n elements and then reads one or two of them. The partition search computes only the boundary that defines the median. It's the same principle as preferring hashing over sorting in Section 1 — don't compute more structure than the question needs.

Against stepping. Same O(m + n) time. Both walk toward the boundary; only one jumps to it.

Why O(log min(m, n)) beats even O(log(m + n)). The bound is in the shorter array, because that's what's being searched. When one array dwarfs the other — a million elements against ten — you do about 3 iterations, not 20. The problem asks for log(m+n); this is strictly better.

The framing worth keeping:

When a quantity is defined by a split rather than by a value, binary search the split point.

The median is the archetype. The same move gives you the k-th element of two sorted arrays (§7), and it's why "search the partition" belongs alongside "search the index" and "search the answer" as the third use of binary search in this section.

5. Java Prerequisites

Sentinels for absent boundaries

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

MIN_VALUE as "no element on this side, so nothing can violate the ≤ check"; MAX_VALUE symmetrically. Since actual values are bounded by 10^6, these can never win a max/min on a valid partition.

Integer vs floating-point division

(a + b) / 2      // int division — truncates. WRONG for the even case
(a + b) / 2.0    // promotes to double

(2 + 3) / 2 is 2; (2 + 3) / 2.0 is 2.5.

The swap via recursion

if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

One level deep only — after the swap the condition is false. An explicit swap of local references works identically and avoids the (trivial) stack frame.

Overflow-safe midpoint — lo + (hi - lo) / 2, as everywhere in this section.

6. Interview Communication Guide

Clarifying questions: Can either array be empty (yes — m or n can be 0, which is what the sentinels handle)? Are both definitely sorted ascending? Return a double? Is O(log(m+n)) a hard requirement (yes — it's the whole question)?

The pitch

"The natural approaches are merging, which is O(m+n) time and space, or stepping to the middle with two pointers, which fixes the space but not the time. Neither meets the O(log(m+n)) requirement.

The reframe is to stop looking for the median's value and start looking for a cut. The median is defined by a split: half the elements on the left, half on the right, with everything on the left ≤ everything on the right. That definition never mentions sorting or merging.

So I cut nums1 after i elements and nums2 after j. Since the left half must hold exactly half the total, choosing i forces j = half − i — one variable, which I can binary search.

Checking a cut is O(1). Within each array the order is already guaranteed, so only the two cross-comparisons can fail: left1 ≤ right2 and left2 ≤ right1. If left1 > right2 I took too many from nums1 and move left; otherwise too few, move right.

Three details make it work. I search the shorter array, so j can never fall outside nums2 — that's what the swap on line one is for. I use ±∞ sentinels at the edges, which collapses four empty-side special cases into the same two comparisons. And half = (m+n+1)/2 puts the extra element on the left when the total is odd, so the odd answer is just max(left1, left2).

O(log min(m,n)) time, O(1) space — better than the required bound when one array is much larger."

Edge cases to volunteer:

The empty-array cases are the ones to name — they're what the sentinels exist for, and a solution handling empties with explicit ifs will have missed at least one of the four combinations.

The uneven-size case is the second — it's what the swap exists for, and without it j goes out of bounds.

7. Follow-Up Questions — Modified Constraints

⭐ "Find the k-th smallest element of the two arrays, not the median."

The same partition search with half replaced by k. The median is the special case k = (m+n+1)/2. Still O(log min(m,n)), and it's a good check of whether you understood the technique or memorized the median formula — if the +1 and the max(left1,left2) were mysterious, this variant exposes it.

⭐ "What about k sorted arrays instead of two?"

The partition idea doesn't extend cleanly — with k arrays there are k−1 free variables rather than one, so there's nothing simple to binary search. Practical options: a min-heap of the k current heads, popping to the median position at O(median · log k); or binary search on the value — count how many elements across all arrays are ≤ a candidate x, which is O(k log n) per check, giving O(k log n · log(range)). The second generalizes better.

"What if the arrays were streams you could only read forwards?"

Binary search needs random access to reach a partition point, so it's out. You'd fall back to the two-pointer step at O(m+n) — or, if only an approximate median is needed, a streaming quantile sketch like t-digest at O(1) memory.

"What if one array were vastly larger — a million against ten?"

This already handles it optimally. Searching the shorter array means about 3 iterations for m = 10, regardless of n. That's why the bound is O(log min(m,n)) rather than O(log(m+n)) — and it's the case where the swap pays off most.

"What if the arrays contained duplicates?"

No change at all. The partition conditions use <=, so ties across the boundary are fine — [5] and [5] gives 5.0. Unlike the rotated-array problems, duplicates cost nothing here, because the validity predicate stays monotonic.

"What if they weren't sorted?"

Then the whole structure collapses — sorting first is O((m+n) log(m+n)), which is worse than the O(m+n) merge-free scan. For an unsorted median the right tool is quickselect at O(m+n) average. Worth naming, because it shows the sortedness is doing all the work here.