Given two arrays nums1 and nums2, each sorted in non-decreasing order, return the median of the combined collection of all their elements.
The median is the middle value once every element from both arrays is merged into one sorted sequence. When the total number of elements is odd, it is the single middle value; when it is even, it is the average of the two middle values. The result is a floating-point number.
Example
Merged: [1, 2, 3]. The middle value is 2.
Constraints
- 0 <= nums1.length, nums2.length <= 1000
- 1 <= nums1.length + nums2.length
- -10^6 <= nums1[i], nums2[i] <= 10^6
- Both nums1 and nums2 are sorted in non-decreasing order.
Intuition
The straightforward approach merges the two sorted arrays into one — a two-pointer walk taking the smaller front each time — then reads the middle value (odd total) or averages the two middle values (even total).
function findMedianSortedArrays(nums1, nums2) {
const merged = [];
let i = 0;
let j = 0;
// Standard merge: repeatedly take the smaller of the two fronts.
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++]); // drain the leftovers
while (j < nums2.length) merged.push(nums2[j++]);
const n = merged.length;
const mid = Math.floor(n / 2);
// Odd total -> the single middle; even total -> average the two middles.
return n % 2 === 1 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;
}This is O(m + n) — and the merge is the slow part. The classic target is O(log(m + n)). Can we do better?
The median only depends on a partition: a cut through each array so that everything on the left is <= everything on the right, with the left side holding exactly half of the combined elements. We never merge — we only need the values straddling that cut. And a cut in one array forces the cut in the other (their left sizes must sum to half), so there is only one free choice: binary-search the cut in the smaller array.
At each candidate cut, look at the four boundary values. Matching the stored solution's names: cut1 is the count taken from nums1, so left1 = nums1[cut1 - 1] and right1 = nums1[cut1] (and likewise left2 / right2 in nums2), with sentinels −∞ / +∞ for an empty side. The cut is correct when maxLeft = max(left1, left2) is <= minRight = min(right1, right2); otherwise the offending side tells you which way to shift — and you discard half the remaining cut positions, the same as a binary search over a sorted array.
In the diagram below, the top axis is that binary search itself: the candidate range [lo, hi] for cut1, halved each step as the probe mid lands (note cut1 jumps 2 → 4 → 3, not +1 at a time). The two rows show the partition that cut1 — and the forced cut2 = half − cut1 — induce, with │ marking each cut; the strip under each step is the derived maxLeft ≤ minRight check that decides which half to keep:
nums1 = [1, 5, 8, 12, 18], nums2 = [2, 4, 9, 11, 15, 20] — binary-search cut1 in the smaller array
half = 6, so the combined left side needs 6 values. cut1 ranges over [0, 5]; probe the midpoint cut1 = 2 → {1, 5} from nums1 and {2, 4, 9, 11} from nums2. But 11 sits left of 8 — nums2 gives up too much, so discard the lower half: lo = 3.
Now cut1 ∈ [3, 5]; probe cut1 = 4 → {1, 5, 8, 12} and {2, 4}. This time 12 is left of 9 — nums1 over-contributes, so discard the upper half: hi = 3.
The range collapses to cut1 = 3 → {1, 5, 8} and {2, 4, 9} on the left. Now every left value is ≤ every right value — the cut is correct.
11 elements in total (odd), so the median is the largest left-side value, maxLeft = max(8, 9) = 9. Merged, the arrays are [1, 2, 4, 5, 8, 9, 11, 12, 15, 18, 20].
Optimization
Merge and pick the middle
Merge the two sorted arrays with a two-pointer walk, advancing whichever side has the smaller front element. Stop once you have collected just past the middle index, then read the middle one (odd total) or average the two middle ones (even total).
O(m + n) time, O(m + n) space — straightforward and correct, though it doesn't hit the O(log(m + n)) target the problem is known for.
function findMedianSortedArrays(nums1, nums2) {
const merged = [];
let i = 0;
let 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;
const mid = Math.floor(n / 2);
return n % 2 === 1 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;
}Binary search on the partition
Binary-search the smaller array for a partition that splits both arrays so every element on the left is <= every element on the right and the two halves have equal size (or the left is one larger). At the correct cut, the median comes from the boundary values maxLeft and minRight. Sentinels (-Infinity / +Infinity) handle empty halves.
O(log(min(m, n))) time, O(1) space — the optimal solution the problem targets.
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length;
const n = nums2.length;
const half = Math.floor((m + n + 1) / 2);
let lo = 0;
let hi = m;
while (lo <= hi) {
const cut1 = Math.floor((lo + hi) / 2);
const cut2 = half - cut1;
const left1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
const right1 = cut1 === m ? Infinity : nums1[cut1];
const left2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
const right2 = cut2 === n ? Infinity : nums2[cut2];
if (left1 <= right2 && left2 <= right1) {
const maxLeft = Math.max(left1, left2);
if ((m + n) % 2 === 1) return maxLeft;
const minRight = Math.min(right1, right2);
return (maxLeft + minRight) / 2;
}
if (left1 > right2) hi = cut1 - 1;
else lo = cut1 + 1;
}
return 0;
}Complexity analysis
Time complexity: O(log(min(m, n))). Here's why:
- The binary search runs over cut positions in the smaller array only (the longer one's cut is derived).
- Each step checks four boundary values in O(1) and halves the candidate cut range.
So the work is logarithmic in the shorter length — overall O(log(min(m, n))). (The merge baseline is O(m + n).)
Space complexity: O(1). Here's why:
- The partition search keeps only the cut bounds and the four boundary values; no merged array is built.
Nothing scales with the inputs — overall O(1). (The O(m + n) merge baseline would also cost O(m + n) space.)
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums1 = [5], nums2 = [5] | 5 | Two single-element arrays — both elements equal, so the median is that value. |
| nums1 = [], nums2 = [2,4,6] | 4 | One array empty — median of [2,4,6] is the middle, 4. |
| nums1 = [1,4], nums2 = [2,3] | 2.5 | Even total — merged [1,2,3,4], average the two middles (2 and 3). |
| nums1 = [10,20,30], nums2 = [15] | 17.5 | Even total — merged [10,15,20,30], average 15 and 20. |
| nums1 = [8], nums2 = [] | 8 | Single element, other array empty — that element is the median. |
| nums1 = [1,2,3], nums2 = [10,20,30] | 6.5 | Disjoint ranges — merged [1,2,3,10,20,30], average 3 and 10. |
Try it yourself
Write your solution against the real judge before checking the reference.