4. Median of Two Sorted Arrays
hardAsked at DRWDRW uses this as a pure algorithmic-difficulty benchmark — O(log(min(m,n))) via binary search on the smaller array. The connection to trading is direct: computing the combined median bid-ask spread from two sorted venue feeds without merging them. Sub-O(n) is the only acceptable answer.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DRW loops.
- Glassdoor (2026-Q1)— DRW SWE onsite candidates report Median of Two Sorted Arrays as a hard-difficulty benchmark problem, graded almost entirely on achieving the O(log(min(m,n))) bound.
- Blind (2025-10)— DRW interview threads note this problem is used to distinguish candidates who know the binary-partition approach from those who only know the O(m+n) merge.
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 = [1,2,3], median = 2.
Example 2
nums1 = [1,2], nums2 = [3,4]2.50000Explanation: Merged array = [1,2,3,4], median = (2+3)/2 = 2.5.
Approaches
1. Binary search on the smaller array (O(log(min(m,n))))
Binary search for a partition of the smaller array such that max(left partition) ≤ min(right partition) across both arrays combined. The median is derived from the elements at the partition boundary.
- Time
- O(log(min(m,n)))
- Space
- O(1)
function findMedianSortedArrays(nums1, nums2) {
// Ensure nums1 is the smaller array
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; // partition index in nums1
const partY = ((m + n + 1) >> 1) - partX; // corresponding partition in nums2
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 === 1) return Math.max(maxLeftX, maxLeftY);
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
} else if (maxLeftX > minRightY) {
hi = partX - 1;
} else {
lo = partX + 1;
}
}
return 0;
}Tradeoff: O(log(min(m,n))) time, O(1) space. The binary search operates on the smaller array. This is the only answer DRW accepts for this problem — O(m+n) merge is mentioned only to be dismissed.
DRW-specific tips
Explain the invariant before writing any code: 'I binary search for a cut in nums1 such that everything left of both cuts is ≤ everything right of both cuts. The total number of elements left of the cut equals half the combined length — this determines the cut position in nums2 given the cut position in nums1.' DRW interviewers will ask: 'What if one of the arrays is empty?' — the algorithm handles this via the -Infinity/+Infinity sentinels. They will also ask: 'What is the kth smallest element across two sorted arrays?' — a generalization of the same binary search.
Common mistakes
- Starting with the O(m+n) merge and presenting it as an answer — you will be told to improve it.
- Not ensuring nums1 is the smaller array — the binary search range [0, m] must cover the smaller array.
- Off-by-one in the partition size calculation — partY must equal (m+n+1)/2 - partX for the left half to have the correct size.
- Not handling the +Infinity/-Infinity sentinels for edge partitions (partX = 0 or partX = m).
Follow-up questions
An interviewer at DRW may pivot to one of these next:
- Kth Smallest Element in Two Sorted Arrays — generalize: find the kth smallest without fully merging.
- How would you find the median of k sorted arrays in O(n log k)?
- What is the probability that the median of two merged uniform distributions [0,1] lies in a given subinterval?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why binary search on the smaller array?
The binary search range is [0, m] where m = smaller array length. If m < n, this is O(log m) < O(log n) — strictly better. Always swap to ensure nums1 is smaller.
What does (m+n+1)/2 represent?
The number of elements in the combined left partition. Using (m+n+1)>>1 handles odd-length combined arrays by giving the left partition one extra element — the median.
When do you return Max(maxLeftX, maxLeftY) directly vs averaging?
For odd total length, the median is the single middle element — the maximum of the left partition. For even length, it is the average of the maximum of the left and the minimum of the right partition.