Master the median of 2 sorted arrays interview with a proof-first partition method, dry run, and 60-second explanation that beats merge-based O(m+n) thinking.
Most candidates who fail the median of two sorted arrays interview question don't fail because they forgot the algorithm. They fail because they can explain the steps but not the reasoning — and the moment an interviewer asks "why does that partition work?", the answer dissolves. Preparing for the median of 2 sorted arrays interview means being able to derive the idea, prove the invariant, and narrate a dry run without reaching for a memorized script.
This guide is built for that exact gap. Not a syntax walkthrough. A proof-first playbook that takes you from the intuition through the correctness argument to a 60-second verbal explanation you can deliver under pressure.
Why This Is a Partition Problem, Not a Merge Problem
The Brute-Force Instinct Is Honest, But It Wastes the Sorted Order
The first instinct is almost always correct in spirit: merge the two arrays, find the middle element. It works. It's O(m + n). And in a time-pressured interview, "correct and readable" can feel like enough.
The problem is that merging throws away the most valuable property the input gives you for free: both arrays are already sorted. A merge reads every element to reconstruct order that already exists. The sorted structure contains enough information to locate the median without ever materializing a combined array — and that's exactly what the LeetCode problem statement expects when it specifies an O(log(m + n)) constraint. A brute-force merge can't satisfy that. Binary search on the partition can.
What This Looks Like in Practice
Take `[1, 3, 8]` and `[7, 9, 10, 11]`. Total elements: 7. The median is the 4th smallest element.
Merging gives you `[1, 3, 7, 8, 9, 10, 11]` — four comparisons minimum to build that, then a direct index. Simple enough on paper. But notice what you didn't need: you never needed to know where 9, 10, or 11 sit relative to each other. You only needed to know that the left half of the combined sequence is `[1, 3, 7, 8]` and the right half is `[9, 10, 11]`. The median is `max(left half)` = 8.
In mock interview coaching, this is the moment that trips candidates up most reliably. They start narrating a merge, get halfway through, and then the interviewer asks "can you do better?" — and they're stuck because they never thought about why sorted order matters. The partition framing reframes the whole problem: you're not finding a value, you're finding a cut.
Derive the O(log(min(m, n))) Search From Sorted-Array Invariants
Start From the Invariant the Arrays Already Give You
Both arrays are sorted. That's the only structural fact you need to derive the optimal solution.
Here's the key insight: the median of the combined sequence is the value that splits all elements into two equal halves where every element on the left is ≤ every element on the right. You don't need to know what those elements are — you just need to find the right cut point.
Each array contributes some elements to the left half and some to the right half. Call the cut point in array A position `i` (meaning `i` elements from A go left) and the cut point in array B position `j`. If the total number of elements is `m + n`, then you need `i + j = (m + n + 1) / 2` (integer division). Once you fix `i`, `j` is determined. There's only one degree of freedom. That's the foundation of the O(log(min(m, n))) solution.
Why the Smaller Array Has to Be the Binary-Search Target
If you binary search on the larger array, you risk `j` going negative when `i` is large — which means you'd need to handle an invalid partition where array B contributes fewer elements than the formula requires. Searching the smaller array guarantees `j` stays non-negative throughout. It also ties the log factor to `min(m, n)`, which is the tightest possible bound.
Practically: always let A be the shorter array. If `m > n`, swap. This is a one-line guard at the top of your implementation and it prevents an entire class of boundary bugs.
What This Looks Like in Practice
Set `low = 0`, `high = m` (the length of the shorter array). Binary search for `i` in `[0, m]`. At each step, compute `j = halfLen - i` where `halfLen = (m + n + 1) / 2`.
Now you have a candidate partition. You don't need to merge anything. You have four values: `A[i-1]` (left max of A), `A[i]` (right min of A), `B[j-1]` (left max of B), `B[j]` (right min of B). The partition is valid when `A[i-1] ≤ B[j]` and `B[j-1] ≤ A[i]`. If not, you adjust `i` and recompute `j`. That's the entire algorithm. According to CLRS (Introduction to Algorithms), binary search on a sorted structure to find a target condition is valid whenever the condition is monotone — and this one is.
Make the Valid Partition Condition Feel Obvious
The Left Side Is Allowed to Be Messy, But Not Out of Order
The partition is valid when two conditions hold simultaneously:
- `leftMaxA ≤ rightMinB`: the largest element from A's left portion doesn't exceed the smallest element from B's right portion.
- `leftMaxB ≤ rightMinA`: the largest element from B's left portion doesn't exceed the smallest element from A's right portion.
That's it. You're not checking that the left half is fully sorted or that you've found a global minimum. You're checking that the left-right boundary is clean: nothing on the left exceeds anything on the right. The binary search partition algorithm works precisely because these two checks are sufficient — once they pass, you've found the median.
What This Looks Like in Practice
Use sentinel values at the boundaries. When `i = 0`, A contributes nothing to the left half, so `leftMaxA = -∞`. When `i = m`, A contributes everything, so `rightMinA = +∞`. Same logic for B.
When `leftMaxB > rightMinA`, B's left side is too large — meaning A's cut is too far left and needs to move right. When `leftMaxA > rightMinB`, A's left side is too large — meaning A's cut is too far right and needs to move left. The direction of movement is determined directly by which check fails. That's the monotonicity that makes binary search valid here.
Dry Run the Ugly Uneven Case Until the Pointer Movement Is Boring
Use an Uneven Pair That Forces the Algorithm to Move Both Ways
Arrays: `A = [2, 6]`, `B = [1, 3, 5, 7, 9]`. Total elements: 7 (odd). Shorter array is A (m=2). `halfLen = (2 + 5 + 1) / 2 = 4`.
Initial state: `low = 0`, `high = 2`.
What This Looks Like in Practice
Iteration 1: `i = (0 + 2) / 2 = 1`, `j = 4 - 1 = 3` `leftMaxA = A[0] = 2`, `rightMinA = A[1] = 6` `leftMaxB = B[2] = 5`, `rightMinB = B[3] = 7` Check: `2 ≤ 7` ✓ and `5 ≤ 6` ✓ → valid partition
Left half is `{A[0], B[0], B[1], B[2]}` = `{2, 1, 3, 5}`. Max of left = `max(leftMaxA, leftMaxB)` = `max(2, 5)` = 5. Total is odd, so median = 5.
That converged in one iteration. Let's try a case that requires movement.
Arrays: `A = [1, 7]`, `B = [2, 3, 5, 6]`. Total: 6 (even). `halfLen = 3`.
Iteration 1: `i = 1`, `j = 2` `leftMaxA = 1`, `rightMinA = 7`, `leftMaxB = 3`, `rightMinB = 5` Check: `1 ≤ 5` ✓ and `3 ≤ 7` ✓ → valid
Left half max = `max(1, 3)` = 3. Right half min = `min(7, 5)` = 5. Even total → median = `(3 + 5) / 2 = 4.0`.
The Part Most People Skip Is the Part Interviewers Care About
Now run `A = [5, 7]`, `B = [1, 2, 3, 4]`. `halfLen = 3`.
Iteration 1: `i = 1`, `j = 2` `leftMaxA = 5`, `rightMinA = 7`, `leftMaxB = 2`, `rightMinB = 3` Check: `5 ≤ 3`? ✗ → `leftMaxA > rightMinB`, so A's cut is too far right. Set `high = i - 1 = 0`.
Iteration 2: `i = 0`, `j = 3` `leftMaxA = -∞`, `rightMinA = 5`, `leftMaxB = 3`, `rightMinB = 4` Check: `-∞ ≤ 4` ✓ and `3 ≤ 5` ✓ → valid
Left max = `max(-∞, 3)` = 3. Right min = `min(5, 4)` = 4. Median = `(3 + 4) / 2 = 3.5`.
That leftward correction — where a failing check tells you exactly which direction to move — is what makes this explainable rather than magical. When you can narrate why you moved `high` down, the interviewer knows you understand the algorithm, not just the code.
Odd and Even Totals Use the Same Split, Not Two Different Tricks
The Total-Length Parity Only Changes Which Value You Return
The partition target `halfLen = (m + n + 1) / 2` works for both odd and even totals because of how integer division rounds. For odd totals, the left half gets one extra element, and the median is simply the maximum of the left half. For even totals, the left and right halves are equal in size, and the median is the average of the left-half maximum and the right-half minimum.
The binary search runs identically either way. You're always looking for the same valid partition condition. Parity only affects the last two lines.
What This Looks Like in Practice
Odd total (m + n = 7): Once the partition is valid, return `max(leftMaxA, leftMaxB)`. No averaging needed.
Even total (m + n = 6): Return `(max(leftMaxA, leftMaxB) + min(rightMinA, rightMinB)) / 2.0`.
The `+ 1` in `halfLen` is the detail that makes this work for odd totals without a separate branch. It biases the left half to be the larger half, so the median is always accessible from the left-max values.
In practice, the parity bug that shows up most often in submissions is integer division when averaging: `(leftMax + rightMin) / 2` in languages with integer arithmetic truncates instead of giving a float. Write `/ 2.0` or cast explicitly. It's a one-character fix that fails a surprisingly large number of test cases if you miss it. Java's integer division behavior and Python's `/` vs `//` distinction are both worth knowing cold before the interview.
Prove the Partition Method Works, Then Make It Interview-Safe
State the Invariant Before You Try to Prove Anything
The claim: if `i + j = halfLen`, `leftMaxA ≤ rightMinB`, and `leftMaxB ≤ rightMinA`, then the left half of the combined sequence contains exactly the `halfLen` smallest elements, and the median is determined.
This is the invariant. State it before the proof, not after. Interviewers respond much better to "here's what I'm going to show" than to a proof that arrives at its own claim as a surprise.
Why the Search Converges
The partition algorithm is valid because the condition `leftMaxA ≤ rightMinB` is monotone in `i`. As `i` increases, `leftMaxA` increases (or stays the same) and `rightMinB` decreases (or stays the same) — because A is sorted and B is sorted, and increasing `i` moves elements from B's right portion into B's left portion. So if the condition fails at position `i`, it will continue to fail for all positions to the right of `i` (when `leftMaxA > rightMinB`) or all positions to the left (when `leftMaxB > rightMinA`). That monotonicity is exactly what makes binary search valid: each comparison eliminates half the remaining search space.
The contradiction argument: suppose a partition is valid but the median is wrong. Then some element on the left exceeds some element on the right — but that contradicts `leftMaxA ≤ rightMinB` and `leftMaxB ≤ rightMinA`. The conditions are both necessary and sufficient. As Sedgewick and Wayne note in Algorithms (4th ed.), binary search is applicable whenever the target condition is monotone over a sorted domain — and this partition condition qualifies exactly.
What This Looks Like in Practice
For an interview, compress the proof into three parts:
- Invariant: "I need `i + j = halfLen` and both cross-comparisons to pass."
- Boundary condition: "If `leftMaxA > rightMinB`, `i` is too large and I move left. If `leftMaxB > rightMinA`, `i` is too small and I move right."
- Convergence: "The conditions are monotone in `i` because both arrays are sorted, so binary search always terminates at the correct partition."
Three sentences. No hand-waving. Interviewers who know the problem will recognize the argument immediately.
Debug the Mistakes That Make Good Solutions Fail Tests
The Bugs Are Usually Boring: Off-by-One, Bounds, and Bad Sentinels
Binary search on the smaller array is the correct approach, but the implementation has exactly four places where bugs cluster:
- `high` initialization: It should be `m` (the length of the smaller array), not `m - 1`. The cut point `i` can be anywhere from 0 to m inclusive.
- `halfLen` formula: `(m + n + 1) / 2` — the `+ 1` is load-bearing for odd totals. Drop it and you get a wrong median for every odd-length input.
- Sentinel values: `leftMaxA` when `i = 0` must be `-∞` (or `Integer.MIN_VALUE`), not `A[0]`. `rightMinA` when `i = m` must be `+∞`, not `A[m-1]`.
- Array swap guard: If you forget to ensure `m ≤ n`, `j` can go negative and you'll get an index error before you reach the partition check.
What This Looks Like in Practice
When a test case fails, check these five values in order before touching the algorithm logic: `i`, `j`, `low`, `high`, and the sentinel values at the boundary. Most wrong-answer submissions have one of these set incorrectly. The algorithm itself is almost never the bug.
A systematic debug trace looks like: "i is 0, j is 5, low is 0, high is 0 — that's consistent. leftMaxA is -∞ (correct, since i=0), rightMinA is A[0]=2 (correct). leftMaxB is B[4]=9, rightMinB is +∞ (correct, since j=5=n). Check: -∞ ≤ +∞ ✓, 9 ≤ 2 ✗ — partition invalid, but low equals high, so the loop exits. That means I'm not handling the case where j exceeds n." That's a concrete bug trace, not a stare-at-the-code session.
The Empty-Array Case Should Be a Shortcut, Not a Surprise
If one array is empty, the median is just the median of the other array — a direct index lookup. Say this out loud in the interview before you start: "If either array is empty, I can return the median of the other one directly. I'll handle that as a guard clause at the top." It signals that you think about edge cases before writing the general solution, which is exactly what interviewers want to see.
Give the 60-Second Answer Interviewers Actually Want to Hear
Say the Idea in Plain English Before You Get Technical
The instinct is to open with "so I'll binary search on the smaller array" — but that's the mechanism, not the idea. Start one level higher.
The script that works: "The key insight is that this is a partition problem. I need to find a cut in each array such that everything on the left of both cuts is ≤ everything on the right. Once I fix how many elements the smaller array contributes to the left half, the larger array's contribution is determined. So I binary search on the smaller array to find the right cut, checking whether the left-max and right-min line up correctly. That gives me O(log(min(m, n))) time."
What This Looks Like in Practice
Full 60-second version (for an interviewer who gives you space):
"This is fundamentally a partition problem. I want to find a split in both arrays where the combined left half contains exactly half the total elements and every element on the left is ≤ every element on the right. If I fix `i` — the number of elements array A contributes to the left — then `j`, array B's contribution, is fully determined. So I binary search on the smaller array for the right value of `i`. At each step, I check whether `leftMaxA ≤ rightMinB` and `leftMaxB ≤ rightMinA`. If both hold, the partition is valid and I can read off the median. If not, the sorted order tells me which direction to move. This runs in O(log(min(m, n))) because I'm binary searching an array of length `min(m, n)`."
Short version (for an interviewer who interrupts):
"It's a partition problem. I binary search the smaller array for a cut point where left-max and right-min line up on both sides. O(log(min(m, n)))."
The median of 2 sorted arrays interview rewards candidates who can state the insight before the code. Practice the full version until you don't need to think about it, then practice the short version for when the interviewer cuts you off after sentence two.
How Verve AI Can Help You Prepare for Your Interview With Median of Two Sorted Arrays
The structural problem with preparing for algorithmic interviews isn't that the material is too hard — it's that rehearsing explanation out loud against a live response is a completely different skill from reading a solution. You can understand every line of the partition algorithm and still freeze when an interviewer asks "why did you move `high` down there?" because you've never actually had to answer that question under pressure.
Verve AI Interview Copilot is built for exactly that gap. It listens in real-time as you narrate your solution, responds to what you actually said rather than a canned prompt, and can push back with the follow-up questions that expose whether you understand the proof or just the syntax. When you're rehearsing the 60-second explanation from the previous section, Verve AI Interview Copilot gives you a live audience that can ask "why is binary search valid here?" — and you'll find out immediately whether your answer holds up. The desktop app stays invisible during actual screen-share sessions, so you can use it as a safety net while you build the confidence to explain the partition method cold. Run the dry run from Section 4, narrate it out loud, and let Verve AI Interview Copilot tell you where your explanation lost the thread. That's the rehearsal loop that turns a memorized algorithm into an explainable one.
FAQ
Q: How do you derive the O(log(min(m,n))) partition solution from the sorted-array property?
Both arrays are sorted, which means you only need to find a cut point — not reconstruct the merged array. Once you fix how many elements the shorter array contributes to the left half, the longer array's contribution is determined. Binary searching the shorter array for that cut point gives the log factor tied to `min(m, n)`.
Q: How do you explain the valid-partition condition in an interview without sounding memorized?
Start from the definition of a median: the value that splits all elements into two equal halves where left ≤ right. Then say: "I need `leftMaxA ≤ rightMinB` and `leftMaxB ≤ rightMinA` — those are just the two cross-checks that confirm nothing on the left exceeds anything on the right." Deriving it from the definition sounds like understanding; reciting it sounds like memorization.
Q: What does the algorithm do when one array is empty or much shorter than the other?
An empty array collapses the problem into a direct median lookup on the non-empty array. State this as a guard clause before the binary search. When one array is much shorter, the algorithm naturally binary searches that shorter array, and the `j` values stay within bounds because you've ensured `m ≤ n` at the start.
Q: How do you handle odd and even total lengths correctly?
The partition target `halfLen = (m + n + 1) / 2` handles both via integer division. For odd totals, the median is `max(leftMaxA, leftMaxB)`. For even totals, it's `(max(leftMaxA, leftMaxB) + min(rightMinA, rightMinB)) / 2.0`. The binary search itself doesn't change — only the final two lines differ.
Q: What are the most common mistakes in binary-search partition indexing?
Off-by-one on `high` (should be `m`, not `m-1`), dropping the `+1` from `halfLen`, incorrect sentinel values at boundaries (`-∞` and `+∞`, not array values), and forgetting to swap arrays so the shorter one is always A. These four bugs account for the vast majority of wrong-answer submissions.
Q: Why is binary search performed on the smaller array only?
Searching the smaller array guarantees `j` stays non-negative throughout the search. If you binary search the larger array, `j` can go negative when `i` is large, producing an invalid partition. It also ensures the time complexity is O(log(min(m, n))) rather than O(log(max(m, n))).
Q: When would a simpler merge-based approach be acceptable in an interview, and why is it not optimal?
A merge-based O(m + n) approach is acceptable when the interviewer explicitly says time complexity isn't a constraint, or as a stated starting point before optimizing. It's not optimal because it ignores the sorted structure of the input — the problem's defining constraint — and can't meet the O(log(m + n)) bound that most interviewers expect for this specific problem.
Conclusion
You came into this knowing the algorithm. You're leaving with the derivation, the proof, the dry run, and a script you can actually say out loud without sounding like you're reading from a card. The median of two sorted arrays problem stops being intimidating the moment you can explain why the partition works — not just that it does.
Before your next interview: rehearse the 60-second script once out loud, start to finish. Then do one full dry run on paper with a pair of arrays you haven't seen before, narrating `i`, `j`, `low`, `high`, and both comparisons at each step. If you can do both without checking your notes, you're ready for the follow-up questions too.
Cameron Wu
Interview Guidance
