4. Median of Two Sorted Arrays
hardAsked at AMDThe logarithmic bound is the whole point of this hard: merging two sorted arrays to grab the middle is trivial, so the O(log(m+n)) requirement exists purely to force the partition insight. AMD candidates report it in performance-critical final rounds, where the bisection mindset transfers directly — the same halving logic an engineer uses to isolate a bottleneck in multi-stream profiler data is what narrows the partition search to the correct split.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in AMD loops.
- Glassdoor (2025-12)— AMD SWE hard-round reports include Median of Two Sorted Arrays as a signal problem for candidates applying to performance-critical roles.
- Blind (2025-08)— AMD interview threads note this as an infrequent but high-signal hard that differentiates strong candidates in final rounds.
Problem
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).
Constraints
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000−10^6 <= nums1[i], nums2[i] <= 10^6
Examples
Example 1
nums1 = [1,3], nums2 = [2]2.00000Explanation: Merged array is [1,2,3]. Median is 2.
Example 2
nums1 = [1,2], nums2 = [3,4]2.50000Explanation: Merged array is [1,2,3,4]. Median = (2+3)/2 = 2.5.
Approaches
1. Two-pointer merge to the midpoint
Advance two pointers in sorted order, but stop as soon as the middle position is reached — no full merged array needed, just the last one or two values seen.
- Time
- O(m+n)
- Space
- O(1)
function findMedianSortedArrays(a, b) {
const total = a.length + b.length;
const stopAt = total >> 1;
let i = 0, j = 0, prev = 0, cur = 0;
for (let step = 0; step <= stopAt; step++) {
prev = cur;
if (i < a.length && (j >= b.length || a[i] <= b[j])) cur = a[i++];
else cur = b[j++];
}
return total % 2 ? cur : (prev + cur) / 2;
}Tradeoff: Linear time but O(1) space — already better than a full merge, and a solid checkpoint to write quickly. It still violates the stated logarithmic requirement, so frame it explicitly as the stepping stone you are about to discard.
2. O(log(min(m,n))) binary search on partition
Binary search on the smaller array to find a partition point. The partition must satisfy: all elements on the left of the combined partition <= all elements on the right. The median is derived from the boundary elements.
- Time
- O(log(min(m,n)))
- Space
- O(1)
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
const m = nums1.length, n = nums2.length;
let lo = 0, hi = m;
while (lo <= hi) {
const partX = (lo + hi) >> 1;
const partY = ((m + n + 1) >> 1) - partX;
const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
const minRightX = partX === m ? Infinity : nums1[partX];
const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
const minRightY = partY === n ? Infinity : nums2[partY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
}
return Math.max(maxLeftX, maxLeftY);
} else if (maxLeftX > minRightY) {
hi = partX - 1;
} else {
lo = partX + 1;
}
}
return 0;
}Tradeoff: O(log(min(m,n))) — strictly better than O(log(m+n)) since we binary search only the smaller array. O(1) space. The partition-validity condition is the key insight: the left half of the combined sorted array must contain (m+n+1)/2 elements.
AMD-specific tips
This problem is about the invariant: the partition divides all 2*(m+n) positions into two halves of equal size, and every element in the left half is <= every element in the right half. Walk through the invariant setup before writing any code — AMD interviewers reward structured thinking. Use -Infinity and +Infinity as sentinels for edge partitions (partX=0 or partX=m) to avoid branchy null checks. Always binary search the shorter array to keep the complexity O(log(min(m,n))).
Common mistakes
- Binary searching the longer array — increases complexity unnecessarily and risks out-of-bounds partY.
- Using (m + n) / 2 instead of (m + n + 1) / 2 for the half-size — the +1 handles the odd-length case by giving one extra element to the left half.
- Forgetting the ±Infinity sentinel for edge partitions — leads to incorrect maxLeft/minRight at boundaries.
- Returning max(maxLeftX, maxLeftY) for even-length arrays — correct for odd; for even you need (max of left + min of right) / 2.
Follow-up questions
An interviewer at AMD may pivot to one of these next:
- Kth Smallest Element in Two Sorted Arrays — generalize to any k, not just the median.
- What if you have k sorted arrays? (Extend to a heap-based approach.)
- How would you compute the median of a streaming data set using two heaps?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why add 1 in (m+n+1)/2?
For odd total length, the median is the middle element. The +1 ensures the left half gets the extra element. For even lengths, the division rounds the same way as without +1, so it doesn't hurt.
Why binary search on the smaller array?
partY = ((m+n+1)/2) - partX. If nums1 is longer, partY could go negative (invalid). By always making nums1 the shorter array, partY is guaranteed to be in [0, n].
Why do the comparisons only check maxLeftX <= minRightY and maxLeftY <= minRightX?
Within each array, sortedness is given for free — maxLeftX <= minRightX always holds. The partition can only be wrong ACROSS the two arrays, so those two cross-checks are necessary and sufficient for every left element to be <= every right element.