Find the Doubled Median of Two Sorted Arrays via Partitioning
Solve this Problemnums1 and nums2, find the median of all the elements combined — without necessarily merging them — returned as double its true value so the answer is always a whole number.
Merging both arrays and reading off the middle works, but it does far more than necessary: only one or two values near the middle actually matter for the answer, yet the full combined array gets built regardless. The faster approach searches directly for a valid split point instead: a cut in the smaller array, paired with a matching cut in the larger one, such that together they divide all the elements into a "left half" and a "right half" of equal size, with every left value at most every right value. Binary search finds that cut in O(log(min(m,n))) guesses — checking just four boundary values per guess — and once a valid split is found, the median is read directly off those boundaries, with the merge step skipped entirely.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums1.length, nums2.length ≤ 6 - ◆
-100 ≤ nums1[i], nums2[i] ≤ 200 - ◆
Both arrays are sorted in non-decreasing order - ◆
Return double the true median, so the answer is always a whole number (avoiding any floating-point comparison)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Merge Both Arrays, Then Read Off the Middle
BruteMerge the two sorted arrays into one sorted array — the same merge step used in merge sort — then read the median straight off the middle of the result (averaging the two middle values when the total count is even). Simple and correct, but building the full merged array costs time and space proportional to the combined size, even though only one or two values near the middle actually matter for the final answer.
O(m + n)O(m + n)1class Solution {
2 public int findDoubledMedian(int[] nums1, int[] nums2) {
3 int m = nums1.length, n = nums2.length;
4 int[] merged = new int[m + n];
5 int i = 0, j = 0, k = 0;
6 while (i < m && j < n) {
7 if (nums1[i] <= nums2[j]) merged[k++] = nums1[i++];
8 else merged[k++] = nums2[j++];
9 }
10 while (i < m) merged[k++] = nums1[i++];
11 while (j < n) merged[k++] = nums2[j++];
12 int total = m + n;
13 if (total % 2 == 1) {
14 return 2 * merged[total / 2];
15 } else {
16 return merged[total / 2 - 1] + merged[total / 2];
17 }
18 }
19}Optimal — Binary Search on the Partition Point
OptimalNever actually merge anything. Instead, search directly for a "cut point" in the smaller array such that, combined with a matching cut point in the larger array, everything to the left of both cuts is exactly half the total count, and every value on the left side is ≤ every value on the right side. Binary search over where that cut in the smaller array should go: at each guess, check the four boundary values around both cuts — if the left side's biggest value ever exceeds the right side's smallest, the guess was too far right (or too far left), so adjust and try again. Once a valid partition is found, the median is derivable directly from those four boundary values, no merging required.
O(log(min(m, n)))O(1)1class Solution {
2 public int findDoubledMedian(int[] numsA, int[] numsB) {
3 int[] nums1 = numsA, nums2 = numsB;
4 if (nums1.length > nums2.length) {
5 int[] tmp = nums1; nums1 = nums2; nums2 = tmp;
6 }
7 int m = nums1.length, n = nums2.length;
8 int lo = 0, hi = m;
9 int half = (m + n + 1) / 2;
10 final int NEG_INF = -1000000, POS_INF = 1000000;
11 while (lo <= hi) {
12 int i = (lo + hi) / 2;
13 int j = half - i;
14 int maxLeft1 = (i == 0) ? NEG_INF : nums1[i - 1];
15 int minRight1 = (i == m) ? POS_INF : nums1[i];
16 int maxLeft2 = (j == 0) ? NEG_INF : nums2[j - 1];
17 int minRight2 = (j == n) ? POS_INF : nums2[j];
18 if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
19 if ((m + n) % 2 == 1) {
20 return 2 * Math.max(maxLeft1, maxLeft2);
21 }
22 return Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2);
23 } else if (maxLeft1 > minRight2) {
24 hi = i - 1;
25 } else {
26 lo = i + 1;
27 }
28 }
29 return -1;
30 }
31}