Median of Two Sorted Arrays: A Step-by-Step Interview Walkthrough
- Jun 22
- 16 min read
Median of Two Sorted Arrays is one of the most famous Hard problems in the interview canon, and its reputation is earned by a single, brutal constraint: the required time complexity is O(log(m + n)). Without that constraint, the problem is trivial — merge the two arrays and grab the middle. With it, you're forced into a binary search, except there's no obvious single sorted array to binary-search over. The whole difficulty is figuring out what to binary-search when the thing you want (the median) is split across two arrays. Candidates who attack the value directly flounder; candidates who reframe the problem as finding a partition — a dividing line through both arrays at once — find an elegant logarithmic solution. Interviewers use it precisely because the naive answer is so easy and the optimal answer is so non-obvious: it tests whether you can find the hidden binary search and then handle the notoriously fiddly boundary conditions without errors. It's a problem where careful reasoning beats raw cleverness.
The median is a robust statistic and combining sorted data from two sources is a real, recurring situation. Distributed databases compute percentiles by merging results from two sorted shards. Latency-monitoring systems find the median response time across two sorted partitions of logs without paying to fully merge them. A/B testing platforms compute combined medians from two sorted result sets. Search and analytics engines merge sorted index segments. Any time you have two already-sorted streams and need a combined order statistic without the cost of a full merge, this is the problem — and the logarithmic solution is what makes it feasible at scale.
Problem Statement
Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array.
The overall run time complexity should be O(log(m + n)).
The median is the middle element if the combined length is odd, or the average of the two middle elements if it's even.
Example:
nums1 = [1, 3], nums2 = [2]
result → 2.0 (the merged array is [1, 2, 3], median 2).
nums1 = [1, 2], nums2 = [3, 4]
result → 2.5 (merged [1, 2, 3, 4], median (2 + 3) / 2).
1. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.
Input: two sorted arrays, nums1 and nums2.
Output: the median of all m + n elements combined, as a floating-point number.
Details to clarify:
Are both arrays already sorted? Yes. That's the property we'll exploit. Without it, no sub-linear solution is possible.
Can either array be empty? Yes. One array could be empty while the other holds all the elements. The solution must handle that.
How is the median defined for an even total? The average of the two middle elements, so the answer can be fractional even if all inputs are integers.
Can the arrays have different lengths? Yes, and as we'll see, deliberately searching the shorter one is part of the trick.
The thing to flag is that the time constraint is doing all the work here. If the interviewer didn't require O(log), you'd merge and be done in five minutes. The moment you see "O(log(m + n))" attached to a problem about sorted arrays, it's a near-certain signal that binary search is expected — the question is binary search on what, since there's no single array to search. Recognizing that the constraint is the actual challenge, and that it points to binary search, is the first real step.
2. Identify the Category of the Question
A few signals jump out:
The inputs are sorted — sorted structure is almost always there to be exploited.
The required complexity is logarithmic — the hallmark of binary search or divide-and-conquer.
We want an order statistic (the median) of the combined data.
That combination — sorted inputs, logarithmic target, find a positional statistic — points squarely at binary search. But this isn't the textbook "search for a value in a sorted array" form, because the median lives across two arrays and we don't know its value in advance. So it belongs to the subtler family of binary search on the answer's structure rather than on a value — closely related to "binary search on the answer" problems, but here we'll search over where to partition the arrays. The same logarithmic instinct as classic binary search, applied to a cleverer search space.
3. Brute Force Solution
Let's think about the naive approach to understand the problem. The definition of the median is "the middle of the combined sorted array," so the most direct method is to build that combined sorted array and read off the middle. Since both inputs are already sorted, we can just copy merge sort: repeatedly take the smaller front element of the two arrays.
merged = merge(nums1, nums2) // like merge sort's merge step
mid = (m + n) / 2
if (m + n) is odd:
return merged[mid]
else:
return (merged[mid - 1] + merged[mid]) / 2This is O(m + n) time and O(m + n) space. We can even trim the space to O(1) by not storing the merged array — just walking two pointers forward until we reach the middle position, tracking the last one or two values. That's O(m + n) time, O(1) space.
But O(m + n) is linear, and the problem demands logarithmic. The brute force is correct but it examines every element to get there. That points to our optimization challenge: can we find those middle elements without walking through all of them? That question is what points us toward something like binary search.
4. Brainstorm More Solutions
Step 1: Look for the structure behind the median
The brute force walks to the middle of the merged array to read off the median's value. Walking is what makes it linear. To see if we can avoid that, let's see if there's some structural fact about the median we could exploit to find it without having to scan for it.
Picture a fully merged array, even though we won't build it. The median lives at its midpoint, and that midpoint splits the merged array into two halves. If we stare at that split for a moment and ask what's actually true about it, two things stand out.
First, the two halves partition all m + n elements between them, and the size of each half is fixed the instant we know m + n. The left half always holds a specific number of elements — exactly (m + n + 1) / 2 elements (using integer division; the + 1 puts the extra element on the left when the total is odd, which will simplify things later).
We also know that, because the array is sorted, the split has a defining order property: every element to the left of it is ≤ every element to its right.
Those two halves are drawn from nums1 and nums2. Can we say anything about which elements of nums1 end up in the left half?
Since nums1 is sorted, the elements that belong on the left — the smaller ones — are exactly its front portion. Same for nums2. So the left half is nothing more than a prefix of nums1 glued to a prefix of nums2. The only piece we're missing is the length of each prefix.
The median, then, is determined entirely by where we cut each array. The turns our question, "find the median value", into "find the right cut points." And cut points are positions, which is a far more searchable kind of target.
Step 2: Count the unknowns — and watch one disappear
A cut on nums1 and a cut on nums2: at first glance, these seem like two independent choices. But before assuming we have to search both arrays, let's check whether the two are really independent, because if they're linked, the problem gets dramatically smaller.
Go back to the fact that pinned down the median in Step 1: the left half has a fixed size, known the moment we see m + n. Suppose we decided to take i elements from the front of nums1. We know that however many of our fixed capacity i does not account for, nums2 must supply the rest. Once we know how many elements we're going to take i elements from num1, we also know exactly how many elements we will need to take from nums2.
That simplifies the problem. We now only have one unknown: how many elements to take from nums1, with the nums2 cut riding along as a consequence. But how do we know which value in that range produces the correct split? How can we tell a correct cut from an incorrect one? And how do we know which way to move when we're wrong?
Step 3: Work out the test for a correct cut
So we pick some number of elements to take from nums1, which fixes the nums2 cut, which fixes both prefixes. How do we know when have we landed on the median's partition rather than some arbitrary one?
We know that a correct split is one where everything on the left is ≤ everything on the right. What would we actually have to check to ensure that property holds? The interesting action is the cut of each array, so let's name the elements on either side of each cut. Picture nums1 split into a left part and a right part. The two elements that touch the cut are the last element of the left part (i.e. the largest one we took from nums1) and the first element of the right part (the smallest one we left behind). We'll call them left1 and right1. Now we do the same for nums2: the last element of its left part is left2, and the first element of its right part is right2.
Now, which "left ≤ right" comparisons should we verify? Within a single array, each array is already sorted, so its own left portion is automatically ≤ its own right portion. The only way the split could be wrong is across arrays: an element taken from one array's left might be larger than an element left behind in the other array's right.
There are exactly two ways that can happen, so there are exactly two conditions to check:
nums1's largest-taken element must not exceed nums2's smallest-remaining element, and the reverse
nums2's largest-taken element must not exceed nums1's smallest-remaining element.
If both hold, no left element anywhere can exceed any right element, and the partition is the median's.
Now let's think about an edge case: a cut can sit at the very start or end of an array, leaving one side with nothing to compare. If we took zero elements from nums1, there is no "largest-taken" on that side. We need to ensure that does not trigger a violation.
One way can do that is to treat a missing left element as -∞ (nothing is too big to be on the left) and a missing right element as +∞ (nothing is too small to be on the right). With those stand-ins, an edge cut satisfies the same two cross-conditions automatically, and we avoid special-casing the boundaries entirely.
Step 4: Figure out which way to move when the cut is wrong
We can now recognize a correct cut, but to do a binary-search, we need one more thing: when a cut fails the test, the failure must tell us which direction to adjust. Let's think through each way that a test can break and see if there's anything that can point us left or right.
Take the first failure: nums1's largest-taken element is bigger than nums2's smallest-remaining element. What does that mean physically? We've dragged an element into nums1's left side that's actually larger than something we left sitting in nums2's right side — so that element doesn't belong on the left at all. We took too many from nums1; the cut is too far to the right. The remedy is to take fewer — move the nums1 cut left.
The second failure is the mirror image: nums2's largest-taken exceeds nums1's smallest-remaining. By the identical reasoning, we took too few from nums1 — an element stranded in nums2's left should have been on the right, and the fix is to pull more into nums1's left by moving its cut to the right. We expand the search to the upper side.
That's everything binary search needs: a single variable, a correctness test, and — when the test fails — an unambiguous signal for which half to keep.
Step 5: Decide which array to search over
We have a working search, but one setup choice determines whether it's robust. We chose to drive the search with the nums1 cut and let the nums2 cut follow. But the follower has to stay legal: the number of elements taken from nums2 can't be negative or exceed its length. When could it go out of range? If nums1 is the longer array, then large choices for its cut demand a negative contribution from nums2 to keep the left half the right size — an impossible, out-of-bounds cut.
The reasoning points straight at the fix: drive the search with the cut on the smaller array. Then the range of choices is bounded by the smaller length, and the forced cut on the larger array always has enough room to stay valid.
Step 6: Read off the median once the cut is correct
When both cross-conditions finally hold, the partition is the median's — now we translate that partition into the answer. Everything on the left is ≤ everything on the right, so the boundary between the halves is pinned between two specific values: the largest element on the left, which is the bigger of the two arrays' largest-taken elements, and the smallest element on the right, the smaller of the two arrays' smallest-remaining elements.
Whether the answer is a single value or the average of two depends on whether the total number of elements is odd or even, so let's handle each case.
If m + n is odd, the combined array has one exact middle element, and we want the left half to contain it. This is why we sized the left half as (m + n + 1) / 2 — rounding up gives the left half the extra element, so the middle element is the last one on the left. That means the median is simply the largest element on the left side: max(left1, left2).
If m + n is even, there is no single middle — the two central elements sit on opposite sides of the cut. The left-hand one is the largest element on the left, max(left1, left2), and the right-hand one is the smallest element on the right, min(right1, right2). The median is their average: (max(left1, left2) + min(right1, right2)) / 2.
Sizing the left half with the + 1 is what makes the odd case resolve to just the left-side maximum, with no extra index handling needed to locate the middle element.
Step 7: Walk through the examples
Odd total. nums1 = [1, 3], nums2 = [2]. Since nums1 is longer, swap so the smaller array is searched: A = [2] (m = 1), B = [1, 3] (n = 2). Total = 3 (odd), half = (1 + 2 + 1) / 2 = 2. Search i ∈ [0, 1]:
i = 0, j = 2. left1 = -∞ (i = 0), right1 = A[0] = 2. left2 = B[1] = 3, right2 = +∞ (j = n). Check: left1 ≤ right2? -∞ ≤ +∞ ✓. left2 ≤ right1? 3 ≤ 2? No. Took too few from A → increase i: lo = 1.
i = 1, j = 1. left1 = A[0] = 2, right1 = +∞ (i = m). left2 = B[0] = 1, right2 = B[1] = 3. Check: 2 ≤ 3 ✓ and 1 ≤ +∞ ✓. Valid! Odd total → median = max(left1, left2) = max(2, 1) = 2.
Merged would be [1, 2, 3], median 2. Correct.
Even total. nums1 = [1, 2], nums2 = [3, 4]. Equal sizes; A = [1, 2], B = [3, 4]. Total = 4 (even), half = (2 + 2 + 1) / 2 = 2. Search i ∈ [0, 2]:
i = 1, j = 1. left1 = A[0] = 1, right1 = A[1] = 2. left2 = B[0] = 3, right2 = B[1] = 4. Check: 1 ≤ 4 ✓; 3 ≤ 2? No. Took too few from A → lo = 2.
i = 2, j = 0. left1 = A[1] = 2, right1 = +∞ (i = m). left2 = -∞ (j = 0), right2 = B[0] = 3. Check: 2 ≤ 3 ✓; -∞ ≤ +∞ ✓. Valid! Even total → median = (max(2, -∞) + min(+∞, 3)) / 2 = (2 + 3) / 2 = 2.5.
Merged would be [1, 2, 3, 4], median 2.5. Correct.
Step 8: Complexity
Let m and n be the two array lengths. We binary-search over the index range of the smaller array, which has size min(m, n). Each step of the binary search does a constant amount of work — computing j, reading four boundary values, and checking two comparisons. Since the number of steps is O(log(min(m, n))), the total time is also O(log(min(m, n))), which satisfies the required time complexity.
Space is O(1) — we only track a handful of indices and values; nothing is allocated proportional to the input. The recursive swap at the start is a single call, not a recursion over data.
By reducing the problem to a one-dimensional problem space, we converted an O(m + n) scan into an O(log) search. The lesson is that when a problem has logarithmic complexity demands on sorted data, the work is usually in finding the right one-dimensional quantity to binary-search — here, the partition point — rather than searching for the answer value directly.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Merge fully, take the middle | O(m + n) | O(m + n) | Simple, but violates the time bound and wastes space |
Two-pointer walk to the midpoint | O(m + n) | O(1) | Better space, still linear — fails the O(log) requirement |
Binary search on the partition | O(log(min(m, n))) | O(1) | The required answer — meets the bound and uses constant space |
The partition-based binary search is the intended solution; the merge approaches are worth describing to show you understand the problem and to motivate why the clever approach is needed (the O(log) constraint rules them out).
6. Pseudocode
ensure nums1 is the smaller array (swap with nums2 if not)
m = len(nums1), n = len(nums2)
half = (m + n + 1) / 2 # size of the combined left half
lo = 0, hi = m
while lo <= hi:
i = (lo + hi) / 2 # take i elements from nums1's left
j = half - i # the rest of the left half from nums2
left1 = (i == 0) ? -infinity : nums1[i - 1]
right1 = (i == m) ? +infinity : nums1[i]
left2 = (j == 0) ? -infinity : nums2[j - 1]
right2 = (j == n) ? +infinity : nums2[j]
if left1 <= right2 and left2 <= right1: # correct partition
if (m + n) is odd:
return max(left1, left2)
else:
return (max(left1, left2) + min(right1, right2)) / 2
else if left1 > right2: # took too many from nums1
hi = i - 1
else: # took too few from nums1
lo = i + 17. Edge Cases
Things to verify before claiming we're done:
One array empty → e.g. nums1 = [], nums2 = [1, 2, 3]. After ensuring nums1 is smaller, m = 0, so i = 0 always, j = half, and the median comes entirely from nums2. The ±∞ sentinels handle the empty side cleanly. ✓
Arrays of very different lengths → searching the smaller one keeps j in bounds and the search short. ✓
All elements of one array smaller than all of the other ([1, 2], [3, 4]) → the partition lands at an array boundary, handled by the infinity sentinels.
Odd vs. even total → the + 1 in half makes odd resolve to the left max; even averages across the partition. Both verified in Step 7.
Single total element ([] and [5]) → half = 1, i = 0, j = 1, median is nums2[0] = 5.
8. Full Code
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Always binary-search the smaller array so that j stays
// in [0, n] and the search runs in O(log(min(m, n))).
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
// size of the combined left half (+1 favors the left)
int half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
// elements taken from nums1's left
int i = (lo + hi) / 2;
// elements taken from nums2's left (forced by i)
int j = half - i;
// Empty side = -infinity on the left, +infinity on the
// right. These sentinels make boundary cuts satisfy
// the cross-conditions automatically.
int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (left1 <= right2 && left2 <= right1) {
// Correct partition: every left element <= every
// right element
if ((m + n) % 2 == 1) {
// odd: median is the left half's max
return Math.max(left1, left2);
}
// even: average the largest left element and
// smallest right element
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
} else if (left1 > right2) {
// took too many from nums1 — cut further left
hi = i - 1;
} else {
// took too few from nums1 — cut further right
lo = i + 1;
}
}
// Reached only if the inputs aren't sorted as promised
throw new IllegalArgumentException("Input arrays must be sorted.");
}
}A note on one subtlety: using Integer.MIN_VALUE / MAX_VALUE as sentinels is fine as long as the real data doesn't itself contain those extreme values; if it might, switch the boundary values and arithmetic to long to avoid a sentinel colliding with a genuine element. For typical interview inputs, the int sentinels are clean and correct.
9. Test the Code
// Odd total
System.out.println(findMedianSortedArrays(new int[]{1, 3}, new int[]{2})); // 2.0
// Even total
System.out.println(findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})); // 2.5
// One array empty
System.out.println(findMedianSortedArrays(new int[]{}, new int[]{1, 2, 3})); // 2.0
// Single total element
System.out.println(findMedianSortedArrays(new int[]{}, new int[]{5})); // 5.0
// Disjoint ranges, very different sizes
System.out.println(findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4, 5, 6})); // 3.5
// All of one array below the other
System.out.println(findMedianSortedArrays(new int[]{1, 2, 3}, new int[]{4, 5, 6})); // 3.5
// Duplicates spanning both arrays
System.out.println(findMedianSortedArrays(new int[]{1, 1, 1}, new int[]{1, 1, 1})); // 1.0These hit the meaningful cases: odd and even totals, an empty array (median entirely from the other), a single total element, arrays of very different sizes, fully disjoint ranges, and duplicates spanning both arrays. The empty-array and different-size cases are the ones that exercise the boundary sentinels and the search-the-smaller-array swap — exactly where naive implementations tend to crash with out-of-bounds errors.
10. Key Lessons
A logarithmic time requirement on sorted data is a near-certain signal for binary search — but the hard part is identifying what to search. When there's no single array to search over, look for a one-dimensional quantity (here, the partition point) whose correctness can be tested and that moves monotonically.
Reframe "find the value" as "find the structure." We never search for the median's value directly; we search for the partition that splits the combined data into equal halves with left ≤ right. Targeting the structure rather than the value is what makes the logarithmic search possible.
Eliminate redundant variables. The partition seemed to need two cuts (i and j), but the fixed left-half size forces j = half - i, collapsing it to a single search variable. Spotting that a second unknown is determined by the first is often what turns a two-dimensional problem into a tractable one-dimensional search.
Use sentinels to unify boundary cases. Treating an empty partition side as ±∞ lets cuts at the array edges pass the same cross-condition checks as interior cuts, eliminating a thicket of special cases — the part of this problem that causes the most bugs.
Search the smaller array. It keeps the derived index in bounds and tightens the complexity to O(log(min(m, n))). A small setup decision (swap if needed) prevents an entire class of out-of-bounds errors.
The thing that makes Median of Two Sorted Arrays click is the reframe from "find the median value" to "find where to cut both arrays so the left half and right half are balanced and ordered." Once you see that the median is defined by a partition, that choosing how much to take from one array forces the rest, and that a too-far-left or too-far-right cut tells you exactly which way to search, the famous Hard problem reduces to a careful binary search over a single number. Training yourself to ask "what's the one quantity I can binary-search here, and how do I know which way to move?" is the habit that turns this and the whole family of binary-search-on-structure problems from intimidating to mechanical.
Good Luck and Happy Coding!
Comments