LeetCode hard solved live
Median of Two Sorted Arrays: Solved Live Interview Walkthrough
A step-by-step ex-FAANG walkthrough for the Median of Two Sorted Arrays interview problem, including intuition, gotchas, optimal binary search, and complexity.
Median of Two Sorted Arrays is a perfect hard interview problem because the obvious solution is almost too easy: merge both arrays, take the middle, and move on. That passes a toy example, but it misses the point of the prompt. A strong interviewer is looking for whether you can preserve sorted-order information instead of throwing it away with a full merge.
Here is how I would solve it live as an ex-FAANG interviewer: start with a correct baseline, name the target invariant, reduce the problem to choosing a clean partition, then make the binary search feel inevitable instead of magical.
1. Restate the problem in interview language
You are given two individually sorted arrays. You need the median of the combined multiset without necessarily materializing that combined array. If the total length is odd, the median is the middle value. If it is even, the median is the average of the two middle values.
The important phrase is individually sorted. The arrays do not have to be the same length, values can repeat, one array can be empty, and every value in one array does not have to be smaller than every value in the other. Those details decide whether your solution is robust or just memorized.
- Example odd total: [1, 3] and [2] combine conceptually to [1, 2, 3], so the median is 2.
- Example even total: [1, 2] and [3, 4] combine conceptually to [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.
- The baseline merge is O(m + n). The optimal interview target is O(log(min(m, n))) because we only binary-search the smaller array.
2. Start with the baseline, then explain why it is wasteful
A baseline merge is not wrong. In fact, saying it first is useful because it proves you understand the median definition. The waste is that merging computes every position even though the median only cares about the boundary between the left half and the right half.
Once you say that out loud, the problem becomes smaller: can we find a split where the left side contains exactly half of the combined elements and every left-side value is less than or equal to every right-side value? If yes, the median is sitting right on that split.
3. The key invariant: a valid partition
Imagine cutting array A after i elements and array B after j elements. Everything before those cuts belongs to the left half; everything after those cuts belongs to the right half. We choose j so the left half has the right size: i + j = floor((m + n + 1) / 2). The plus one is a neat trick that lets odd and even totals use the same logic.
A partition is valid when the largest value on the left of A is less than or equal to the smallest value on the right of B, and the largest value on the left of B is less than or equal to the smallest value on the right of A.
- leftA <= rightB
- leftB <= rightA
- If both are true, all left-half elements are <= all right-half elements.
4. Why binary search works
We binary-search i, the cut position in the smaller array. Then j is forced by the left-half size. If leftA is greater than rightB, we took too many elements from A, so move i left. If leftB is greater than rightA, we took too few elements from A, so move i right.
That is the whole algorithm. The hard part is not the code; it is trusting the monotonic direction. Because both arrays are sorted, moving the cut left in A can only reduce leftA and increase or preserve rightA. Moving the cut right in A can only increase leftA and reduce or preserve rightA. That gives binary search a real ordering to exploit.
5. Clean TypeScript solution
The sentinel values remove edge-case branches when a cut sits at the beginning or end of an array. Negative infinity means there is no value on that side of the left partition; positive infinity means there is no value on that side of the right partition.
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
let shorter = nums1;
let longer = nums2;
if (shorter.length > longer.length) {
[shorter, longer] = [longer, shorter];
}
const totalLength = shorter.length + longer.length;
const leftSize = Math.floor((totalLength + 1) / 2);
let low = 0;
let high = shorter.length;
while (low <= high) {
const cutShorter = Math.floor((low + high) / 2);
const cutLonger = leftSize - cutShorter;
const leftShorter = cutShorter === 0 ? -Infinity : shorter[cutShorter - 1];
const rightShorter = cutShorter === shorter.length ? Infinity : shorter[cutShorter];
const leftLonger = cutLonger === 0 ? -Infinity : longer[cutLonger - 1];
const rightLonger = cutLonger === longer.length ? Infinity : longer[cutLonger];
if (leftShorter <= rightLonger && leftLonger <= rightShorter) {
if (totalLength % 2 === 1) {
return Math.max(leftShorter, leftLonger);
}
return (Math.max(leftShorter, leftLonger) + Math.min(rightShorter, rightLonger)) / 2;
}
if (leftShorter > rightLonger) {
high = cutShorter - 1;
} else {
low = cutShorter + 1;
}
}
throw new Error("Input arrays must be sorted.");
}6. Walk through the classic example
Take nums1 = [1, 3] and nums2 = [2]. We search the shorter array, so shorter = [2] and longer = [1, 3]. The total length is 3, so leftSize = 2. If we cut shorter after 0 elements, j becomes 2, so the left side is [1, 3]. That fails because leftLonger = 3 is greater than rightShorter = 2. We need more from the shorter array, so move right.
Now cut shorter after 1 element and longer after 1 element. The left boundary values are 2 and 1; the right boundary values are Infinity and 3. Both partition checks pass. The total length is odd, so return max(2, 1) = 2.
7. Gotchas that usually break candidates
- Searching the larger array: j can fall outside the other array. Always swap so the binary search happens on the smaller input.
- Using floor((m + n) / 2) for the left side: for odd totals, floor((total + 1) / 2) keeps the median in the left partition, which simplifies the return logic.
- Forgetting empty arrays: sentinels make [] and [1] return 1 without special-case code.
- Confusing indices and counts: cutShorter is a count of left-side elements, not the index of the current value.
- Averaging the wrong two values for even totals: use max(left boundary) and min(right boundary), not arbitrary values around one array's cut.
8. Complexity and interview summary
Time complexity is O(log(min(m, n))) because every iteration halves the search space of the smaller array. Space complexity is O(1) because the algorithm stores only cut positions and boundary values. No merged array is created.
A crisp interview summary sounds like this: I need a partition where the left half has the correct size and every left value is <= every right value. I binary-search the cut in the smaller array and derive the other cut. If the A-left boundary is too large, move left; if the B-left boundary is too large, move right. Once the partition is valid, the median is either the max left boundary or the average of max left and min right.
Still stuck on your own problem? Book a live 55-min session with an ex-FAANG engineer — first session $49.
Next step
Want live feedback instead of another solo debugging session?
Crackr keeps the scope tight: one blocker, one senior engineer, one session designed to turn confusion into a repeatable pattern.