Median of Two Sorted Arrays
Problem
nums1 (size m) and nums2
(size n), each sorted in ascending order. Return the median of all
m + n values taken together (average of the two middle values when the total
is even). The target running time is O(log(m + n)).[1,3], [2]Output2.0[1,2], [3,4]Output2.50 ≤ m, n ≤ 1000 · 1 ≤ m + n ≤ 2000 · -106 ≤ nums[i] ≤ 106 · Required: O(log(m+n)) time.
Try it yourself
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
}
}
i come from nums1 fixes the count from
nums2 (j = half - i), so we only binary search one cut in
the shorter array until left max ≤ right min on both sides.Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.
Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.
Open the Binary Search guide →Approaches
Brute ForceConcatenate & Sort
O((m+n) log(m+n))Space O(m+n)Ignore that the inputs are sorted: copy both into one array, sort it, and read the middle element(s). Correct, but it throws away the sortedness we were given.
public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] all = new int[nums1.length + nums2.length]; System.arraycopy(nums1, 0, all, 0, nums1.length); System.arraycopy(nums2, 0, all, nums1.length, nums2.length); Arrays.sort(all); int n = all.length; if (n % 2 == 1) return all[n / 2]; return (all[n / 2 - 1] + all[n / 2]) / 2.0; }
Trivial to write, but wastes both the sorted input and extra memory.
BetterMerge Walk to the Middle
O(m+n)Space O(1)Run the merge step of merge sort with two pointers, but don't store the
merged array — just remember the last two values seen (prev,
cur) and stop after index total/2.
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 k = 0; k <= total / 2; k++) { prev = cur; if (j >= n || (i < m && nums1[i] <= nums2[j])) cur = nums1[i++]; else cur = nums2[j++]; } return total % 2 == 1 ? cur : (prev + cur) / 2.0; }
Linear and constant memory, yet still misses the logarithmic requirement.
OptimalBinary Search on the Partition
O(log min(m,n))Space O(1)Binary search the cut px in the shorter array; the cut in the
other is py = (m+n+1)/2 - px. If maxX > minY we took too
many from nums1 (move left); if maxY > minX too few (move
right). Missing neighbours act as ±∞.
public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int x = nums1.length, y = nums2.length; int low = 0, high = x; while (low <= high) { int px = (low + high) / 2; int py = (x + y + 1) / 2 - px; int maxX = px == 0 ? Integer.MIN_VALUE : nums1[px - 1]; int minX = px == x ? Integer.MAX_VALUE : nums1[px]; int maxY = py == 0 ? Integer.MIN_VALUE : nums2[py - 1]; int minY = py == y ? Integer.MAX_VALUE : nums2[py]; if (maxX <= minY && maxY <= minX) { if ((x + y) % 2 == 1) return Math.max(maxX, maxY); return ((double) Math.max(maxX, maxY) + Math.min(minX, minY)) / 2; } else if (maxX > minY) { high = px - 1; // too many from nums1 } else { low = px + 1; // too few from nums1 } } throw new IllegalArgumentException("inputs not sorted"); }
Dry runnums1=[1,3,8], nums2=[7,11,18,19]
- px=1138|7111819maxY 18 > minX 3 → low=2
- px=2138|7111819maxY 11 > minX 8 → low=3
- px=3138|71118198≤11, 7≤∞ → 8 ✔
Meets the log bound with O(1) memory — the expected interview answer.
py can never go negative or past
the end of the longer one.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Concatenate & Sort | O((m+n) log(m+n)) | O(m+n) |
| Better | Merge Walk to the Middle | O(m+n) | O(1) |
| Optimal | Binary Search on the Partition | O(log min(m,n)) | O(1) |
- Binary searching the longer array —
pycan fall out of range. - Integer division for the even case — divide by
2.0(or cast) to keep the .5. - Forgetting empty sides: use
±∞sentinels when a cut is at 0 or the end.
- Start with the merge walk, then ask: “do we need every element before the middle?”
- Explain the partition condition before coding; the code follows from it.
- Using
(m+n+1)/2puts the extra element on the left, so odd totals returnmaxLeft.