Median of Two Sorted Arrays

BINARY SEARCH · HARD

Builds on Day 13: Binary Search Variations

The optimal solution below binary searches on a PARTITION INDEX rather than a value, the trickiest variation covered in that lesson; read it first if that idea is still new.

The problem

Given two arrays nums1 (size m) and nums2 (size n), each already sorted ascending, return the median of the combined m + n values — the middle value if the combined length is odd, or the average of the two middle values if it’s even. Example: nums1=[1,3], nums2=[2] → combined is [1,2,3], median 2.0. nums1=[1,2], nums2=[3,4] → combined is [1,2,3,4], median (2+3)/2 = 2.5. The catch that makes this a Hard: you’re asked to do it in O(log(min(m,n))) time — actually constructing the combined array first is too slow, so the optimal solution below never builds it at all.

Solution 1: Brute force — linear merge, then read the middle

This is the honest, obvious approach: since both inputs are already sorted, merge them into one sorted array using the same two-pointer walk from the merge step of merge sort — at each step, compare the two pointers’ current values and push whichever is smaller, advancing that pointer. Once one array is exhausted, append the remainder of the other. Once the full merged array exists, the median is just an index lookup: the middle element for odd length, or the average of the two middle elements for even length. It’s a real, correct algorithm — but it’s not the O(log(min(m,n))) the problem asks for, because it touches every element of both arrays at least once, no matter how the median is computed.

nums1 = [2, 4, 5], nums2 = [1, 6, 7, 9] — combined length 7 (odd), median: 5

NUMS1

NUMS2

MERGED (growing)

Press Play or Step to begin.

Step 0 / 13

▶ Play↺ Reset

The code

function medianBruteForce(nums1, nums2) {
  const merged = [];
  let i = 0, j = 0;

  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) merged.push(nums1[i++]);
    else merged.push(nums2[j++]);
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);

  const n = merged.length;
  if (n % 2 === 1) return merged[(n - 1) / 2];
  return (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Line by line:

• The first while loop is the classic merge-sort merge step: as long as both pointers are still in range, compare the two current values and push whichever is smaller, advancing only that pointer. Using <= (not <) keeps the merge stable, though for a median that choice doesn’t actually change the answer.
• Once one array runs out, exactly one of the next two while loops fires — it appends whatever’s left of the other array, which is already sorted, so no more comparisons are needed.
• n % 2 === 1 picks the single middle element directly by index for an odd combined length; the else branch averages the two elements straddling the middle for an even length.
• Every element of both inputs ends up inside merged at least once — that full construction, not the final index lookup, is what the complexity below is really paying for.

Complexity

Time	Space	Approach
O(m+n)	O(m+n)	Two-pointer merge builds the full combined array, then an O(1) index lookup finds the median

Solution 2: Optimal — binary search the smaller array’s partition point

The merged array never needs to exist — only its middle needs to be identified. Any way of splitting both arrays into a “left half” and a “right half” so that every left-half value is ≤ every right-half value, and the two halves are the correct sizes, has found the median without merging anything: it’s max(leftHalf) (odd total) or the average of max(leftHalf) and min(rightHalf) (even total). Binary search directly for that split.

First, swap nums1/nums2 if needed so nums1 is always the smaller array — call it A (size m), and the other B (size n). Binary search a partition index i in A, in the range [0, m]. Once i is chosen, the matching partition index j in B is forced — it’s whatever makes the left side hold exactly ⌈(m+n)/2⌉ elements total, computed in O(1) as j = half - i. Compare the boundary elements: maxLeft(A) <= minRight(B) and maxLeft(B) <= minRight(A). If both hold, the split is valid — read off the median. If maxLeft(A) is too big, i is too high, search lower; otherwise search higher. When i is at an array boundary (0 or m), there’s no real element on that side, so -Infinity / Infinity sentinels stand in — they can never be the reason a comparison fails, which is exactly the point: an empty side should never block a valid split.

Same nums1=[2, 4, 5], nums2=[1, 6, 7, 9] as Solution 1 — nums1 is already the smaller array, so no swap needed; the binary search takes 3 tries to converge, and the resulting median (5) matches Solution 1 exactly.

SMALLER ARRAY — binary searched (A)

LARGER ARRAY — partition derived in O(1) (B)

Press Play or Step to begin.

Step 0 / 7

▶ Play↺ Reset

The code

function medianOptimal(nums1, nums2) {
  let A = nums1, B = nums2;
  if (A.length > B.length) { const t = A; A = B; B = t; }
  const m = A.length, n = B.length;

  let lo = 0, hi = m;
  const half = Math.floor((m + n + 1) / 2);

  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2);
    const j = half - i;

    const maxLeftA = i === 0 ? -Infinity : A[i - 1];
    const minRightA = i === m ? Infinity : A[i];
    const maxLeftB = j === 0 ? -Infinity : B[j - 1];
    const minRightB = j === n ? Infinity : B[j];

    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      if ((m + n) % 2 === 1) return Math.max(maxLeftA, maxLeftB);
      return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
    } else if (maxLeftA > minRightB) {
      hi = i - 1;
    } else {
      lo = i + 1;
    }
  }
  throw new Error('input arrays must be sorted');
}

Line by line:

• The swap guarantees A is always the smaller-or-equal-size array, so the binary search range [0, m] below is always bounded by min(m,n) — this one swap is the entire reason the complexity is log(min(m,n)) and not log(max(m,n)).
• half = Math.floor((m + n + 1) / 2) is the exact left-half size that works for both parities: it’s (total+1)/2 for odd totals (the extra element lands on the left) and total/2 for even totals — one formula, no branching.
• Given a candidate i, j = half - i is not searched — it’s the only value of j that makes the combined left side exactly half elements, derived in O(1).
• The four maxLeft/minRight lines use -Infinity / Infinity sentinels exactly when a partition sits at an array’s edge (nothing real on that side) — this is essential: without it, an edge partition would either read undefined or crash on A[-1], and every comparison below would break silently.
• Both cross-conditions holding means the split is valid: read the median directly, no averaging needed for odd totals, averaging the two boundary values for even ones.
• maxLeftA > minRightB means too many elements were taken from A’s left — shrink i by moving hi down; the opposite case grows i by moving lo up. Every iteration halves the search range, giving O(log m) total iterations.

Complexity

Time	Space	Approach
O(log(min(m,n)))	O(1)	Binary search a partition index in the smaller array only; the larger array’s matching partition is always an O(1) derivation, never itself searched

Complexity comparison

Solution	Time	Space
Brute force (linear merge)	O(m+n)	O(m+n)
Optimal (partition binary search)	O(log(min(m,n)))	O(1)

This is a genuine asymptotic improvement, not just a constant-factor speedup — going from linear in the combined size to logarithmic in the smaller size. The min(m,n) is specific and earned, not a loose bound: searching the smaller array bounds the number of binary-search iterations by that array’s size, and the larger array’s matching partition is always derivable from the smaller array’s current guess in O(1) — it never needs its own search. If the roles were reversed (searching the larger array), the algorithm would still be correct, just O(log(max(m,n))) — strictly worse whenever the arrays differ in size, which is exactly why the swap-to-smaller step at the top of Solution 2 isn’t optional.

Interview corner

Why binary search specifically the SMALLER array, rather than either array or always the larger one?

• The binary search range is [0, m] where m is the length of whichever array is being searched — so the number of iterations is bounded by that array’s size, not the other one’s.
• The matching partition index in the OTHER array is always derivable in O(1) from the chosen index (j = half - i) — it never needs a search of its own, so its size doesn’t affect the iteration count at all.
• Choosing to search the larger array instead would still be correct, just O(log(max(m,n))) — strictly worse (or equal) whenever the two sizes differ, which is why the problem’s stated bound is specifically log(min(m,n)), not just “logarithmic”.

Why does half = Math.floor((m + n + 1) / 2) correctly handle BOTH odd and even combined lengths with one formula, no branch?

• For an odd total, the true median is a single element that must sit as the last element of the left half — that requires the left half to hold (total + 1) / 2 elements, one more than a plain half-split.
• For an even total, (total + 1) / 2 floors back down to exactly total / 2 — an even split, which is what’s needed so the median can be averaged from the boundary of each side.
• Because integer division floors automatically, one expression produces the “+1 for odd, exact half for even” behavior without an if (total % 2) branch anywhere in the partition math.

What would break if the -Infinity / Infinity sentinels were removed and A[i - 1] / A[i] were read directly even at the array’s edges?

• At i = 0, A[i - 1] is A[-1] — plain array indexing never throws in JS, it just silently returns undefined, which then poisons every downstream comparison (any comparison against undefined evaluates to false).
• At i = m, A[i] is out of bounds the same way — also undefined, also silently wrong instead of throwing where the bug would be obvious.
• The sentinels exist precisely so an empty side (nothing taken from this array’s left, or nothing left on its right) can never be the reason a valid split gets rejected — a real, common case whenever the two input arrays differ a lot in size, like nums1=[1] against a 7-element nums2.

Trick question — what does this log?

const partitionState = { maxLeftA: -Infinity, minRightA: 4 };
console.log(JSON.stringify(partitionState));

• Answer: {"maxLeftA":null,"minRightA":4} — NOT {"maxLeftA":-Infinity,"minRightA":4}, and NOT a dropped key either.
• JSON.stringify has no way to represent Infinity, -Infinity, or NaN in JSON (they aren’t valid JSON number literals) — its actual behavior is to silently convert any of them to null, while keeping the key.
• That’s different from undefined: an undefined-valued property is dropped from the output entirely, not converted to null — two different “missing-ish” values, two different serialization behaviors.

Trap: this is exactly why nobody should try to JSON.stringify the partition state above for debugging or logging — every boundary sentinel silently becomes null, which reads as “no data” rather than “this side of the partition is empty,” actively misleading whoever’s debugging. The sentinels are fine to use in live comparisons (-Infinity <= 4 works exactly as expected); they just can’t survive a round trip through JSON.

Quiz

1. Why is the brute-force merge solution O(m+n), not O(log(min(m,n)))?

Show answer

It walks every element of both arrays once during the merge, so its cost scales linearly with the total size. The brute-force merge is a two-pointer walk that visits every element of both arrays exactly once before it can even look up the middle — that’s O(m+n) work no matter how few values are ultimately needed for the median.

2. The optimal solution binary searches a partition index. Why in the SMALLER of the two arrays specifically?

Show answer

Because the number of binary-search iterations is bounded by that array’s size, and the larger array’s partition is always derived in O(1) — never searched itself. Binary searching the smaller array bounds the number of iterations by min(m,n). The matching partition index in the OTHER array is always derived in O(1) from the current guess, so its size never factors into the iteration count at all — that’s the entire reason the bound is specifically log(min(m,n)).

3. What do the -Infinity / Infinity sentinels represent when the partition index i equals 0 or m?

Show answer

There’s no real element on that side of the partition (it’s empty) — the sentinel guarantees it can never wrongly fail a boundary comparison. At i = 0, A[i - 1] is A[-1] — plain array indexing never throws in JS, it just silently returns undefined, which then poisons every downstream comparison (any comparison against undefined evaluates to false). The sentinels exist precisely so an empty side can never be the reason a valid split gets rejected — a real, common case whenever the two input arrays differ a lot in size.

4. Why does half = Math.floor((m + n + 1) / 2) correctly size the left partition for BOTH odd and even combined lengths, with no explicit parity branch?

Show answer

Integer division makes it equal (total+1)/2 for odd totals and exactly total/2 for even totals — one formula covers both cases. Math.floor((m + n + 1) / 2) equals (total+1)/2 for odd totals (giving the left half the extra middle element) and floors back down to exactly total/2 for even totals — one expression handles both parities without an explicit odd/even branch.

5. For nums1=[2,4,5], nums2=[1,6,7,9] (7 total elements, odd), the algorithm finds a valid partition with maxLeftA=5 and maxLeftB=1. What’s the median?

Show answer

5 — max(maxLeftA, maxLeftB), since the total length is odd. For an odd combined length, once a valid partition is found the true median is whichever boundary value is larger — max(maxLeftA, maxLeftB) — since together the two maxLeft values are exactly the largest element(s) of the correctly-sized left half.