37. Median of Two Sorted Arrays
You are given two arrays nums1 (length m) and nums2 (length n), each sorted in non-decreasing order. Return the median of all m + n numbers taken together.
The median is the middle value of the combined sorted sequence; when the total count is even, it is the average of the two middle values, so the answer can be fractional (answers within 10^-5 are accepted).
A merge gives O(m + n). Aim for O(log(min(m, n))).
Input: nums1 = [1,4], nums2 = [2,7,9] Output: 4.0
Explanation: Combined, the values are [1,2,4,7,9]; the middle one is 4.
Input: nums1 = [1,3], nums2 = [2,4] Output: 2.5
Explanation: Combined: [1,2,3,4], so the median is (2 + 3) / 2 = 2.5.
Input: nums1 = [], nums2 = [5] Output: 5.0
Constraints
0 <= m, n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
💡 Hint 1
The median splits the combined values into a left part and a right part of (almost) equal size, where everything on the left is <= everything on the right.
💡 Hint 2
If you take i elements from nums1 for the left part, the size forces you to take half - i from nums2. So only i needs to be chosen.
💡 Hint 3
Binary search i over the shorter array: check the four values around the cut. If nums1[i-1] > nums2[j], take fewer from nums1; if nums2[j-1] > nums1[i], take more.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Instead of merging, binary search for the cut that splits the combined values into a left half of size half = floor((m + n + 1) / 2) and a right half. Work on the shorter array (swap if needed). Choosing i elements from nums1 for the left side forces j = half - i from nums2. The cut is correct when nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], treating out-of-range neighbors as -∞ / +∞. If nums1[i-1] is too big, move i left; otherwise move it right. Once the cut is valid, the median is the largest left value when m + n is odd, and the average of the largest left value and the smallest right value when it is even. The search range is [0, min(m, n)], hence the logarithmic time.
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length;
const n = nums2.length;
const half = (m + n + 1) >> 1;
let lo = 0;
let hi = m;
while (lo <= hi) {
const i = (lo + hi) >> 1;
const j = half - i;
const left1 = i > 0 ? nums1[i - 1] : -Infinity;
const right1 = i < m ? nums1[i] : Infinity;
const left2 = j > 0 ? nums2[j - 1] : -Infinity;
const right2 = j < n ? nums2[j] : Infinity;
if (left1 <= right2 && left2 <= right1) {
const leftMax = Math.max(left1, left2);
if ((m + n) % 2 === 1) return leftMax;
return (leftMax + Math.min(right1, right2)) / 2;
}
if (left1 > right2) hi = i - 1;
else lo = i + 1;
}
return 0;
}class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length, half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
int i = (lo + hi) / 2, j = half - i;
int left1 = i > 0 ? nums1[i - 1] : Integer.MIN_VALUE;
int right1 = i < m ? nums1[i] : Integer.MAX_VALUE;
int left2 = j > 0 ? nums2[j - 1] : Integer.MIN_VALUE;
int right2 = j < n ? nums2[j] : Integer.MAX_VALUE;
if (left1 <= right2 && left2 <= right1) {
int leftMax = Math.max(left1, left2);
if ((m + n) % 2 == 1) return leftMax;
return (leftMax + (double) Math.min(right1, right2)) / 2.0;
}
if (left1 > right2) hi = i - 1;
else lo = i + 1;
}
return 0.0;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
function findMedianSortedArrays(nums1, nums2) {
}Run your code to see results here.