You're given two arrays, nums1 and nums2, each already sorted in non-decreasing order, with lengths m and n. Imagine merging them into one sorted list — return the median of that combined list.
m + n is odd, the median is the single middle value.Return the answer as a decimal number (for example, 2.50000).
The twist that makes this problem famous: merging takes O(m + n) time, but the required time complexity is O(log (m + n)) — you must find the median without walking through both arrays.
(2 + 3) / 2 = 2.5), so the return type is a floating-point number in every case — convert with float(...) / (double) / float64(...) before returning.i = 0 or i = m, and the -inf / +inf sentinels stand in for the missing borders.j = half - i stays within 0..n only when nums1 is the shorter array; searching the longer one lets j go negative. It also gives the tighter bound O(log min(m, n)).<=, so equal values on either side of the cut are perfectly fine — nothing assumes distinctness.half replaced by k: binary search how many of the first k elements come from one array, or recursively discard k/2 elements from one array per step. The median is just the special case k = (m + n + 1) / 2.x, count elements <= x in each array with binary search (O(k log n) per guess), and narrow until the count matches the median rank.Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 The merged order is [1,2,3]; the middle value is 2.
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 The merged order is [1,2,3,4]; the median is (2 + 3) / 2 = 2.5.
- nums1.length == m - nums2.length == n - 0 <= m <= 1000 - 0 <= n <= 1000 - 1 <= m + n <= 2000 - -10^6 <= nums1[i], nums2[i] <= 10^6 - nums1 and nums2 are each sorted in non-decreasing order
Two sorted arrays, one median, and a time limit that forbids merging — this is the definitive test of whether you can binary search on structure instead of values. The arc: merge (obvious), walk to the middle (leaner), then the partition trick that answers in logarithmic time by looking at just four numbers.
In plain English: pretend the two arrays are merged into one sorted list and report its median — but you may not actually build that list.
Formally: given sorted arrays nums1 (length m) and nums2 (length n) with 1 <= m + n <= 2000, return the median of their combined multiset as a double, in O(log (m + n)) time.
Worked example 1 — nums1 = [1,3], nums2 = [2]
virtual merge: [1, 2, 3] (never actually built)
^
odd total → median = 2.00000
Worked example 2 — nums1 = [1,2], nums2 = [3,4]
virtual merge: [1, 2, 3, 4]
^ ^
even total → median = (2 + 3) / 2 = 2.50000
A senior candidate pins down the input guarantees before writing a line — this problem has two traps (empty arrays, even totals) that good questions surface immediately.
“Are both arrays individually sorted, and can I rely on that?”
Yes — the entire logarithmic solution leans on sortedness. If they were unsorted, nothing beats O(m + n) after a sort.
“Can the arrays contain duplicates or negative numbers?”
Both — and neither breaks anything. The partition logic only compares values, never assumes uniqueness.
“Can one of the arrays be empty?”
Yes, m can be 0 (only the sum m + n is at least 1). The answer is then just the median of the other array — your cut must be allowed to take zero elements from either side.
“For an even total, do I return the lower middle or the average?”
The average of the two middle values, as a decimal — 2.50000, not 2.
“How large can m + n get?”
Up to 2000 here — small enough that a merge passes the judge, but the required complexity is O(log (m + n)), so the partition solution is the real deliverable.
Before I code, a few quick checks.
I'll assume both arrays are individually sorted non-decreasing — that is the property my whole approach depends on.
One array can be completely empty, so my cut must be able to take zero elements from either array.
And for an even total I'll return the average of the two middle values as a decimal.
The median splits the combined m + n values into a left half and a right half. To compute it you only need two numbers: the maximum of the left half and the minimum of the right half. You never need the halves to be internally ordered — so you never need the merge.
left half right half
[.. .. .. maxL] | [minR .. .. ..]
odd → median = maxL
even → median = (maxL + minR) / 2Say the left half must hold half = (m + n + 1) / 2 elements. If you decide to take i elements from the front of nums1, you have no choice left: exactly j = half - i elements must come from the front of nums2. One unknown, not two — the search space is just the value of i, from 0 to m.
Because both arrays are sorted, a cut (i, j) is valid exactly when the four border values interleave: left1 <= right2 and left2 <= right1. If left1 > right2, you took too much from nums1 — slide left (hi = i - 1). If left2 > right1, you took too little — slide right (lo = i + 1). Each check is O(1) and halves the range: O(log min(m, n)) total, comfortably within O(log (m + n)).
| Merge and index | Two pointers | Partition binary search | |
|---|---|---|---|
| Time | O(m + n) | O(m + n) | O(log min(m, n)) |
| Space | O(m + n) | O(1) | O(1) |
Full, runnable code for all three lives in the Approaches selector below.
Key takeaway
When a problem asks for the k-th element of data you'd normally merge, don't merge — binary search the cut position and validate it with a constant number of border comparisons. The median is just the halfway cut.
ensure nums1 is the shorter array (swap if needed)
half = (m + n + 1) / 2
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) / 2 # take i from nums1's left
j = half - i # forced take from nums2's left
if left1 > right2: hi = i - 1 # cut in nums1 too far right
elif left2 > right1: lo = i + 1 # cut in nums1 too far left
else: answer from max(left1, left2) and min(right1, right2)