0
lo
Given two sorted arrays, find the combined median in O(log min(m, n)) time by binary-searching a partition of the shorter array so the left halves of both arrays together equal the right halves — no merging needed.
Given two sorted arrays nums1 and nums2, return the median of the combined sorted sequence. The required time complexity is O(log(m+n)). Concrete example: nums1=[1,3], nums2=[2,4]. Combined sorted: [1,2,3,4]. Even length, so median = (2+3)/2 = 2.5. Another example: nums1=[1,2], nums2=[3,4,5]. Combined: [1,2,3,4,5], median = 3 (middle element).
i in the shorter array. The matching index j = half - i in the longer array is determined automatically. When maxLeft(A) ≤ minRight(B) AND maxLeft(B) ≤ minRight(A), the partition is correct and the median falls out of those four boundary values — no element-by-element scan required.A be the shorter array (m ≤ n) so the binary search space is O(log m) — we only ever search A.half = ⌊(m+n)/2⌋. This is how many elements belong in the combined left half.i = (lo+hi)/2 in A; derive j = half - i in B. Left side of both = first i+j elements of the merged sequence.±Infinity sentinels for empty sides: maxLeft1, minRight1 from A; maxLeft2, minRight2 from B.maxLeft1 ≤ minRight2 and maxLeft2 ≤ minRight1 → correct partition. Compute median: odd total → min(minRight1, minRight2); even total → (max(maxLeft1,maxLeft2)+min(minRight1,minRight2))/2.maxLeft1 > minRight2, A's left is too large → move hi = i-1. Otherwise, B's left is too large → move lo = i+1.min(minRight1, minRight2), not max(maxLeft1, maxLeft2). The left half holds ⌊(m+n)/2⌋ elements, so the median sits at the front of the right half. Many people reach for the max of the left half first and get confused when the partition sizes are different.The naive merge costs O(m+n) time and space — easy to code but violates the problem's O(log(m+n)) requirement. Two-pointer scanning without allocating is still O(m+n). The binary-search partition is the only approach that hits the logarithmic bar.
maxLeft ≤ minRight as the invariant to enforce, the adjustment rule (move left or right) follows automatically.i so that left halves of A and B together have 2 elements.1function findMedianSortedArrays(nums1: number[], nums2: number[]): number {2 // Binary search on the shorter array for O(log min(m,n))3▶ let A = nums1;4▶ let B = nums2;5▶ if (A.length > B.length) [A, B] = [B, A];67▶ const m = A.length;8▶ const n = B.length;9▶ const half = Math.floor((m + n) / 2);1011▶ let lo = 0;12▶ let hi = m;1314 while (lo <= hi) {15 const i = Math.floor((lo + hi) / 2); // partition A: A[0..i-1] | A[i..m-1]16 const j = half - i; // partition B: B[0..j-1] | B[j..n-1]1718 const maxLeft1 = i === 0 ? -Infinity : A[i - 1];19 const minRight1 = i === m ? Infinity : A[i];20 const maxLeft2 = j === 0 ? -Infinity : B[j - 1];21 const minRight2 = j === n ? Infinity : B[j];2223 if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {24 // Correct partition — left halves contain exactly half elements25 if ((m + n) % 2 === 1) {26 return Math.min(minRight1, minRight2);27 }28 return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;29 } else if (maxLeft1 > minRight2) {30 hi = i - 1; // A's left side too large — shrink it31 } else {32 lo = i + 1; // B's left side too large — grow A's left side33 }34 }3536 throw new Error('Input arrays are not sorted');37}
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
// Binary search on the shorter array for O(log min(m,n))
let A = nums1;
let B = nums2;
if (A.length > B.length) [A, B] = [B, A];
const m = A.length;
const n = B.length;
const half = Math.floor((m + n) / 2);
let lo = 0;
let hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2); // partition A: A[0..i-1] | A[i..m-1]
const j = half - i; // partition B: B[0..j-1] | B[j..n-1]
const maxLeft1 = i === 0 ? -Infinity : A[i - 1];
const minRight1 = i === m ? Infinity : A[i];
const maxLeft2 = j === 0 ? -Infinity : B[j - 1];
const minRight2 = j === n ? Infinity : B[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// Correct partition — left halves contain exactly half elements
if ((m + n) % 2 === 1) {
return Math.min(minRight1, minRight2);
}
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
} else if (maxLeft1 > minRight2) {
hi = i - 1; // A's left side too large — shrink it
} else {
lo = i + 1; // B's left side too large — grow A's left side
}
}
throw new Error('Input arrays are not sorted');
}A.length ≤ B.length bounds the binary search to O(log m) where m is the smaller size. Without this swap, we might search the longer array unnecessarily.half = ⌊(m+n)/2⌋ is how many elements belong in the combined left partition. Because integer division floors, for an odd total the right side has one extra — the median element.i cuts A so A[0..i-1] is its left side. j = half - iforces B's partition to make up the rest of the left half. This is the key coupling: adjustingi automatically adjusts j.i=0, A's left is empty, so maxLeft1 = -Infinity — it trivially satisfies the inequality. When i=m, A's right is empty, so minRight1 = +Infinity. Same logic for B. These sentinels eliminate special cases for empty sides.maxLeft1 > minRight2, A gave too many large elements to the left — decrease hi. Otherwise B did, so increase lo. Because A and B are sorted and we search A's range, the loop converges in at most O(log m) iterations.maxLeft ≤ minRight uses non-strict inequality, so equal boundary values are fine.half = ⌊(m+n)/2⌋ with the target rank k, then use the same partition logic. The median is just the k-th element where k = (m+n)/2.i=0, maxLeft1=-Infinity, so the condition is trivially satisfied and the answer comes from B alone.O((m+n) log(m+n)) — much worse. The partition binary search is strictly better for two sorted inputs.function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
// Binary search on the shorter array for O(log min(m,n))
let A = nums1;
let B = nums2;
if (A.length > B.length) [A, B] = [B, A];
const m = A.length;
const n = B.length;
const half = Math.floor((m + n) / 2);
let lo = 0;
let hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2); // partition A: A[0..i-1] | A[i..m-1]
const j = half - i; // partition B: B[0..j-1] | B[j..n-1]
const maxLeft1 = i === 0 ? -Infinity : A[i - 1];
const minRight1 = i === m ? Infinity : A[i];
const maxLeft2 = j === 0 ? -Infinity : B[j - 1];
const minRight2 = j === n ? Infinity : B[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// Correct partition — left halves contain exactly half elements
if ((m + n) % 2 === 1) {
return Math.min(minRight1, minRight2);
}
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
} else if (maxLeft1 > minRight2) {
hi = i - 1; // A's left side too large — shrink it
} else {
lo = i + 1; // B's left side too large — grow A's left side
}
}
throw new Error('Input arrays are not sorted');
}Walk two pointers forward, counting up to the middle index without ever building the merged array — the simple fallback if you blank on the logarithmic partition.
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
const total = m + n;
// We need the elements at positions (total-1)/2 and total/2 of the merged
// sequence. For odd total these coincide; for even we average them.
const upper = Math.floor(total / 2); // index of the second middle element
const lower = upper - 1 + (total % 2); // index of the first middle element
let i = 0; // pointer into nums1
let j = 0; // pointer into nums2
let prev = 0; // value at the previous merged position
let curr = 0; // value at the current merged position
for (let count = 0; count <= upper; count++) {
prev = curr;
if (i < m && (j >= n || nums1[i] <= nums2[j])) {
curr = nums1[i];
i++;
} else {
curr = nums2[j];
j++;
}
}
if (lower === upper) {
return curr; // odd total: the single middle element
}
return (prev + curr) / 2; // even total: average the two middles
}upper + 1times, tracking only the two values straddling the median. It is linear, so it fails the problem's O(log(m+n)) requirement — but it is the most natural thing to write under pressure and a perfect correctness baseline.Discard k/2 elements from one array each step, halving k — a different framing of the logarithmic solution that generalizes cleanly to any rank.
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
const total = nums1.length + nums2.length;
// Returns the k-th smallest (1-indexed) across nums1 and nums2, searching
// within nums1[s1..] and nums2[s2..].
const kth = (s1: number, s2: number, k: number): number => {
// If one array is exhausted, the answer is straight from the other.
if (s1 >= nums1.length) return nums2[s2 + k - 1];
if (s2 >= nums2.length) return nums1[s1 + k - 1];
// Base case: the smallest remaining head is the 1st element.
if (k === 1) return Math.min(nums1[s1], nums2[s2]);
// Probe the (k/2)-th element of each remaining slice; clamp to array end.
const half = Math.floor(k / 2);
const i = Math.min(s1 + half, nums1.length) - 1;
const j = Math.min(s2 + half, nums2.length) - 1;
if (nums1[i] <= nums2[j]) {
// nums1[s1..i] are all too small to be the k-th — discard them.
return kth(i + 1, s2, k - (i - s1 + 1));
}
// Otherwise discard nums2[s2..j].
return kth(s1, j + 1, k - (j - s2 + 1));
};
if (total % 2 === 1) {
return kth(0, 0, Math.floor(total / 2) + 1);
}
const left = kth(0, 0, total / 2);
const right = kth(0, 0, total / 2 + 1);
return (left + right) / 2;
}⌊k/2⌋ candidates, so k roughly halves per step and recursion depth is O(log(m+n)). Clamping the probe index to the array end is what keeps it safe when one slice is shorter than k/2.| "median of two sorted arrays" | binary search partition on shorter array |
| "O(log(m+n)) required" | partition binary search, not element binary search |
| need k-th element across two sorted lists | half = k, same partition logic |
| empty-side edge case in partition | ±Infinity sentinels for boundary values |
let A = nums1, B = nums2;
if (A.length > B.length) [A, B] = [B, A];
const m = A.length, n = B.length;
const half = Math.floor((m + n) / 2);
let lo = 0, hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2);
const j = half - i;
const maxLeft1 = i === 0 ? -Infinity : A[i - 1];
const minRight1 = i === m ? Infinity : A[i];
const maxLeft2 = j === 0 ? -Infinity : B[j - 1];
const minRight2 = j === n ? Infinity : B[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// found — return median
} else if (maxLeft1 > minRight2) hi = i - 1;
else lo = i + 1;
}maxLeft(A) ≤ minRight(B) AND maxLeft(B) ≤ minRight(A)— every left-side element is ≤ every right-side element.nums1=[1,3], nums2=[2,4]. What is the median?nums1=[], nums2=[1,2,3]. What is the median?