ASAPUtils
The reframe
Merging both arrays is easy but O(m+n), which violates the requirement. The median only needs the boundary between the combined left and right halves—not the full merged order.
Choose partition i in shorter array A. The required partition in B is forced:
half = floor((m + n + 1) / 2)
j = half - i
Now compare only four boundary values.
Valid partition conditions
Aleft <= Bright
Bleft <= Aright
If both hold, every value on the combined left is no greater than every value on the combined right.
- Odd total → median is
max(Aleft, Bleft). - Even total → average
max(left boundaries)andmin(right boundaries).
C++ solution
double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
if (a.size() > b.size()) return findMedianSortedArrays(b, a);
int total = a.size() + b.size();
int half = (total + 1) / 2;
int l = 0, r = a.size();
while (l <= r) {
int i = l + (r - l) / 2;
int j = half - i;
int aL = i ? a[i - 1] : INT_MIN;
int aR = i < a.size() ? a[i] : INT_MAX;
int bL = j ? b[j - 1] : INT_MIN;
int bR = j < b.size() ? b[j] : INT_MAX;
if (aL <= bR && bL <= aR) {
if (total % 2) return max(aL, bL);
return (double(max(aL, bL)) + min(aR, bR)) / 2.0;
}
if (aL > bR) r = i - 1;
else l = i + 1;
}
return 0;
}
JavaScript solution
function findMedianSortedArrays(a, b) {
if (a.length > b.length) return findMedianSortedArrays(b, a);
const total = a.length + b.length;
const half = Math.floor((total + 1) / 2);
let l = 0, r = a.length;
while (l <= r) {
const i = l + Math.floor((r - l) / 2);
const j = half - i;
const aL = i ? a[i - 1] : -Infinity;
const aR = i < a.length ? a[i] : Infinity;
const bL = j ? b[j - 1] : -Infinity;
const bR = j < b.length ? b[j] : Infinity;
if (aL <= bR && bL <= aR) {
if (total % 2) return Math.max(aL, bL);
return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
}
if (aL > bR) r = i - 1;
else l = i + 1;
}
}
How the direction works
Aleft > Bright: A placed too many large values on the left → move A’s partition left.- Otherwise
Bleft > Aright: A contributed too few values → move A’s partition right.
One comparison chooses the direction, and the partition search is logarithmic.
Complexity
O(log(min(m,n))) time and O(1) extra space. No merged array is constructed.
Traps
- Searching the longer array.
- Using
(m+n)/2without the+1, which complicates odd totals. - Confusing partition counts with element indices.
- Forgetting empty-side sentinels.
- Averaging two C++ integers before converting to floating point.
- Memorising the code without drawing the four boundaries. The drawing is the algorithm.
Blank re-solve prompt
Draw two sorted rows, choose partitions with the correct combined left size, label four boundary values, and derive both inequalities before writing code.