24. Median of Two Sorted Arrays
hardAsked at MonzoTwo already-sorted arrays, one combined median, and a hard O(log) requirement that forbids merging them — this is the partition binary search at its purest. Monzo candidates report it appearing in senior backend loops, where the banking flavor is genuine: ledger snapshots arrive pre-sorted from storage, and percentile questions over two of them ('median transaction amount across both accounts') reward exactly this no-merge thinking. The interview is won or lost on whether you can DEFEND the partition condition, not type it.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Monzo loops.
- LeetCode (2026)— Problem #4 'Median of Two Sorted Arrays' — canonical statement, bounds, and the O(log(m+n)) requirement.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Monzo interview prep.
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 == m, nums2.length == n0 <= m, n <= 10001 <= m + n <= 2000Either array may be empty — sentinel infinities at the partition edges must cover i = 0, i = m, j = 0, j = n.
Examples
Example 1
nums1 = [1,3], nums2 = [2]2.00000Explanation: Three combined values [1,2,3]: odd total, so the median is the middle element 2 — equivalently max(left half) when the halves split 2/1.
Example 2
nums1 = [1,2], nums2 = [3,4]2.50000Explanation: Four combined values: even total, so the median averages the two boundary values across the partition — (2 + 3) / 2.
Approaches
1. Merge then index
Merge both sorted arrays into one and pick the middle element(s).
- Time
- O(m+n)
- Space
- O(m+n)
const merged = [];
let i = 0, j = 0;
while (i < nums1.length && j < nums2.length) merged.push(nums1[i] < nums2[j] ? nums1[i++] : nums2[j++]);
while (i < nums1.length) merged.push(nums1[i++]);
while (j < nums2.length) merged.push(nums2[j++]);
const t = merged.length;
return t % 2 ? merged[(t-1)/2] : (merged[t/2 - 1] + merged[t/2]) / 2;Tradeoff: Linear time and space, and it discards the problem's strongest hint — that both inputs arrive sorted. It is worth thirty seconds as the correctness baseline; staying here on a hard-rated question concedes the round's actual content.
2. Binary search the smaller array
Partition the shorter array; binary search for the partition where the left halves of both arrays together are exactly half of the combined elements and the boundary values satisfy the median condition.
- Time
- O(log min(m,n))
- Space
- O(1)
function findMedianSortedArrays(a, b) {
if (a.length > b.length) [a, b] = [b, a];
const m = a.length, n = b.length, half = (m + n + 1) >> 1;
let lo = 0, hi = m;
while (lo <= hi) {
const i = (lo + hi) >> 1;
const j = half - i;
const aL = i === 0 ? -Infinity : a[i - 1];
const aR = i === m ? Infinity : a[i];
const bL = j === 0 ? -Infinity : b[j - 1];
const bR = j === n ? Infinity : b[j];
if (aL <= bR && bL <= aR) {
if ((m + n) % 2) return Math.max(aL, bL);
return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
} else if (aL > bR) hi = i - 1; else lo = i + 1;
}
}Tradeoff: Logarithmic in the smaller array, constant space — the expected destination. Its cost is fragility under pressure: four boundary values, sentinel infinities, and the +1 in the half computation each hide an off-by-one. Rehearse narrating the invariant; the code follows from it, not the other way around.
Monzo-specific tips
Monzo candidates report the differentiator is articulating the partition invariant before coding: 'the left halves together hold floor((m+n+1)/2) elements, and the split is correct when max(left) <= min(right) on both cross-checks.' Banking context gives free depth if invited — medians beat means for transaction analytics precisely because card-payment distributions have heavy tails, and percentile queries over pre-sorted ledger snapshots should never pay for a merge. Always binary-search the shorter array and say why: it keeps j = half - i in range and minimizes iterations.
Common mistakes
- Searching the longer array — j = half - i can leave the valid range and index out of bounds.
- Omitting the +1 in half = (m + n + 1) / 2 — odd-total medians land on the wrong side of the partition.
- Skipping sentinel infinities at the four edges — empty arrays and full-side partitions are the judge's favorite tests.
- Returning max(aL, bL) for even totals — even lengths must average the two middle values, returned as a float.
Follow-up questions
An interviewer at Monzo may pivot to one of these next:
- Kth smallest element in two sorted arrays — replace half with k in the same partition argument.
- Median of k sorted arrays — pairwise partitions stop working; discuss binary search on the VALUE domain instead.
- Sliding-window median (LC 480) — the streaming cousin where balanced heaps replace partitioning.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why must the binary search run on the smaller array?
Two reasons: correctness — j = half - i stays within the larger array's bounds for every i — and speed, since iterations are log of the SMALLER length. Searching the longer array can produce negative j and is the most common crash in live attempts.
What do the -Infinity / +Infinity sentinels actually represent?
An empty side of a partition. If i = 0, array A contributes nothing to the left half, so its 'left boundary' must never win a max() — negative infinity encodes that. The sentinels collapse four edge cases into the main comparison.
Why is max(left) <= min(right) sufficient for correctness?
Within each array, sortedness already orders elements. The only orderings the partition could violate are across arrays — aL vs bR and bL vs aR. If both hold, every left element is <= every right element, which is the definition of a valid median split.