Double the Median When Merging Two Sorted Price Lists
Solve this Problemprices1 and prices2, each already sorted in non-decreasing order (possibly empty, but never both at once), imagine them merged into one combined sorted list without actually building it. Return double the median of that combined list — doubling keeps the answer a whole number even when the true median would otherwise be a fraction (the average of two middle values), so the function never needs to return anything other than an integer.
The direct approach merges the two lists first (an easy O(m+n) two-pointer walk, since both are already sorted) and then reads off the middle value or values. That works, but it does far more work than necessary just to find one or two positions near the middle. The faster approach never builds the merged list at all: it binary searches directly for the partition pointBinary Search on the PartitionInstead of searching over array values or over a range of candidate answers, this binary search hunts for a cut position (an index) in the shorter array. A cut is valid once every value kept on its left side is ≤ every value kept on its right side across both arrays combined — exactly the ordering a real merge would produce, found without ever performing the merge. — the single cut position in the shorter list that splits both lists' combined values cleanly into a "left half" and a "right half," with every left value ≤ every right value. Once that cut is found, the median (doubled) is read directly off its boundary values, in O(log(min(m, n))) time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ length of prices1 ≤ 1000 - ◆
0 ≤ length of prices2 ≤ 1000 - ◆
prices1 and prices2 are never both empty - ◆
-10⁶ ≤ prices1[i], prices2[i] ≤ 10⁶ - ◆
Both prices1 and prices2 are sorted in non-decreasing order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Merge Both Lists, Then Read Off the Middle
BruteSince both prices1 and prices2 are already individually sorted, merge them the classic merge-sort way: walk two pointers, always taking whichever front value is smaller, until one list runs out, then copy over whatever's left of the other. Once the full merged list exists, read off its middle value (odd total) or the sum of its two middle values (even total) — returned directly as a doubled value so the result is always a whole number, with no floating-point division required anywhere. Correct and only O(m+n), but it builds the entire merged list just to read one or two values near the middle.
O(m + n)O(m + n)1class Solution {
2 public int doubledMedianPrice(int[] prices1, int[] prices2) {
3 int m = prices1.length, n = prices2.length;
4 int[] merged = new int[m + n];
5 int i = 0, j = 0, k = 0;
6 while (i < m && j < n) {
7 if (prices1[i] <= prices2[j]) merged[k++] = prices1[i++];
8 else merged[k++] = prices2[j++];
9 }
10 while (i < m) merged[k++] = prices1[i++];
11 while (j < n) merged[k++] = prices2[j++];
12
13 int total = m + n;
14 if (total % 2 == 1) {
15 return merged[total / 2] * 2;
16 } else {
17 return merged[total / 2 - 1] + merged[total / 2];
18 }
19 }
20}Optimal — Binary Search on the Partition
OptimalThe merge above builds the entire combined list just to read one or two values near its middle — wasteful once the lists get large. Instead, binary search directly for the correct partition: pick a cut position i in the shorter list (swap first if prices1 is the longer one) and let j be forced by i so the left side always holds exactly half of the combined values. If the two lists' boundary values disagree — one side's rightmost "kept" value exceeds the other side's leftmost "discarded" value — shift the cut and try again. That disagreement always points in one consistent direction, which is exactly what makes the cut position searchable in O(log(min(m, n))) instead of scanning every value.
O(log(min(m, n)))O(1)1class Solution {
2 private static final int NEG = -2000000000, POS = 2000000000;
3
4 public int doubledMedianPrice(int[] prices1, int[] prices2) {
5 int[] a = prices1, b = prices2;
6 if (a.length > b.length) { int[] t = a; a = b; b = t; }
7 int m = a.length, n = b.length;
8 int lo = 0, hi = m;
9 int half = (m + n + 1) / 2;
10 while (lo <= hi) {
11 int i = lo + (hi - lo) / 2;
12 int j = half - i;
13 int aLeft = (i == 0) ? NEG : a[i - 1];
14 int aRight = (i == m) ? POS : a[i];
15 int bLeft = (j == 0) ? NEG : b[j - 1];
16 int bRight = (j == n) ? POS : b[j];
17 if (aLeft <= bRight && bLeft <= aRight) {
18 int maxLeft = Math.max(aLeft, bLeft);
19 if ((m + n) % 2 == 1) return maxLeft * 2;
20 int minRight = Math.min(aRight, bRight);
21 return maxLeft + minRight;
22 } else if (aLeft > bRight) {
23 hi = i - 1;
24 } else {
25 lo = i + 1;
26 }
27 }
28 return -1;
29 }
30}