Loading…

hardBinary SearchLC #4Frequently asked

Median of Two Sorted Arrays

Q: How do you solve Median of Two Sorted Arrays using the Merge (or Half-Merge) with Two Pointers — Baseline approach?

When to use it: Mention first to anchor correctness and the O(m+n) cost, then pivot to the logarithmic partition the prompt demands. Step two pointers through `nums1` and `nums2`, always taking the smaller current element, until you've consumed `(m + n) / 2 + 1` elements; remember the last one or two to form the median. **Why mention it.** It's the obviously-correct reference and a clean way to define what the median *is*, which helps you reason about the faster method. **Why it's not the final answer.** It's `O(m + n)`. The prompt explicitly asks for `O(log(m + n))`, so we have to avoid touching every element. Time complexity: O(m + n). Space complexity: O(1).

LCPractice

Binary Search · 6 of 16 · 13 min

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)).

In plain English

The median splits all m+n values into a lower half and an upper half of equal size. We never build the merged array; instead we find a 'cut' through both arrays so the lower half has the right count and every lower element ≤ every upper element. The four elements straddling the cut give the median.

Examples

Example 1

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Note: Merged = [1,2,3], odd length, median is the middle element 2.

Example 2

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Note: Merged = [1,2,3,4], even length, median = (2 + 3) / 2 = 2.5.

Example 3

Input: nums1 = [], nums2 = [1]
Output: 1.0
Note: One array empty; sentinels make the single element the median.

Constraints

nums1.length == m
nums2.length == n
0 ≤ m ≤ 1000
0 ≤ n ≤ 1000
1 ≤ m + n ≤ 2000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

Clarifying questions4First question: Can one of the arrays be empty?Explore questions

Q1.Can one of the arrays be empty?
Yes — m or n can be 0 (but not both). The ±∞ sentinels at the borders make an empty array behave correctly with no special-casing.
Q2.Is the total length odd or even — how does that change the answer?
Odd total → median is the single middle element (max of the two left borders). Even total → average of the two middle elements (max of left borders and min of right borders).
Q3.Do the arrays share values or have duplicates?
Both possible. The partition condition uses ≤, so equal border values still satisfy a valid cut.
Q4.Is O(m+n) acceptable, or must it be logarithmic?
The prompt insists on O(log(m+n)). I'll present the merge baseline for clarity, then deliver the O(log(min(m,n))) partition solution that meets the bound.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Don't merge — binary search a *partition*. Split the combined arrays into a left part and a right part of the right sizes so that everything on the left ≤ everything on the right. Binary search the cut position in the smaller array (the cut in the larger one is then forced), checking the four border elements. When `leftA ≤ rightB` and `leftB ≤ rightA`, the median falls out of those four values. O(log(min(m, n))) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can reach the O(log(min(m,n))) partition method (or at least the O(log(m+n)) k-th element method) and handle the brutal edge cases — empty sides, odd/even totals, equal borders — without bugs.

Where candidates slip

Binary searching the larger array (wrong complexity), mishandling the empty-partition borders (index out of bounds), or botching the odd/even median formula.

How to stand out

State the merge baseline and its O(m+n), then pivot to 'binary search the cut', explain the ±∞ sentinel trick that kills all the edge cases, and derive j from i so the left half size is fixed.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Merge (or Half-Merge) with Two Pointers — Baseline	`O(m + n)`	`O(1)`	Mention first to anchor correctness and the O(m+n) cost, then pivot to the logarithmic partition the prompt demands.	Read
2	Binary Search the Partition (Optimal)Optimal	`O(log(min(m, n)))`	`O(1)`	The answer they want. Frame it as 'binary search the cut in the smaller array' and emphasize the ±∞ sentinels.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewcut A at i, derive cut B at j = half - iAleft <= Bright AND Bleft <= Aright?YesAleft > BrightExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Merge (or Half-Merge) with Two Pointers — Baseline

TimeO(m + n)SpaceO(1)

Mention first to anchor correctness and the O(m+n) cost, then pivot to the logarithmic partition the prompt demands.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you merged the two sorted arrays, where would the median sit?

2Hint 2Explore hint

You don't need the full merge — just advance two pointers until you've passed (m+n)/2 elements, tracking the middle one or two.

3Hint 3Explore hint

It's O(m+n) and trivially correct. Use it to sanity-check, but the prompt wants O(log(m+n)).

A · Core idea

Step two pointers through nums1 and nums2, always taking the smaller current element, until you've consumed (m + n) / 2 + 1 elements; remember the last one or two to form the median.

Why mention it. It's the obviously-correct reference and a clean way to define what the median is, which helps you reason about the faster method. Why it's not the final answer. It's O(m + n). The prompt explicitly asks for O(log(m + n)), so we have to avoid touching every element.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums1 = [1, 3], nums2 = [2]

take min(1,2)=1

count=1, advance nums1

Statelast = 1

Final result2.0

C · Code with teaching comments

Reference implementation previewpublic double findMedianSortedArrays(int[] a, int[] b) { int m = a.length, n = b.length, total = m + n; int i = 0, j = 0; int prev = 0, curr = 0; for (int count = 0; count <= total / 2; count++) {Explore the full code

solution.javaJava

Merge (or Half-Merge) with Two Pointers — Baseline — reference

3 teaching notes

1
public double findMedianSortedArrays(int[] a, int[] b) {
2
    int m = a.length, n = b.length, total = m + n;
3
    int i = 0, j = 0;
4
    int prev = 0, curr = 0;
5
    // Advance just past the middle — no need to merge the whole thing.
6
    for (int count = 0; count <= total / 2; count++) {
7
        prev = curr;
8
        // Pick the smaller head; the bounds checks handle an exhausted array.
9
        if (i < m && (j >= n || a[i] <= b[j])) {
10
            curr = a[i++];
11
        } else {
12
            curr = b[j++];
13
        }
14
    }
15
    if (total % 2 == 1) {
16
        return curr;
17
    }
18
    // Even total → average the two central elements.
19
    return (prev + curr) / 2.0;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m + n) timeO(1) spaceOpen the invariant and proofExplore the proof

The merge baseline reveals the goal precisely: we only care about the one or two elements at the centre, not the whole merge. That observation — 'we just need the right position, not the full order' — is what motivates binary searching a partition.

ComplexityO(m + n) time, O(1) space — Walk both arrays once with two pointers, stopping at the middle — linear in the total length, constant memory.

E · Edge cases and pitfalls3O(m+n) — fails the asymptotic requirement even though it passes the tests.Explore edge cases

Pitfalls

O(m+n) — fails the asymptotic requirement even though it passes the tests.
Off-by-one on how many elements to consume for odd vs even totals.
Forgetting the j >= n / i < m guards when one array runs out.

03.2

Approach 2 of 2 · Optimal

Binary Search the Partition (Optimal)

TimeO(log(min(m, n)))SpaceO(1)

The answer they want. Frame it as 'binary search the cut in the smaller array' and emphasize the ±∞ sentinels.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine drawing one vertical cut through each array so that the combined left side has exactly half the elements. What must be true about the four values touching the cut for it to be the median split?

2Hint 2Explore hint

Fix the total left-size to (m+n+1)/2. Then the cut position j in B is forced once you choose the cut i in A — so you only search i.

3Hint 3Explore hint

Search i in the SMALLER array. A cut is valid when Aleft ≤ Bright and Bleft ≤ Aright. If Aleft > Bright, your A-cut is too far right; otherwise too far left. Use ±∞ for out-of-range borders.

A · Core idea

Find, without merging, a partition that places exactly the lower half of all elements on the left.

Reframe the median as a cut. A median splits the m + n values into a left part and a right part where (a) the left part has a fixed size and (b) every left value ≤ every right value. If we cut nums1 after index i (so i elements of A go left) and nums2 after index j (so j elements of B go left), then the left part has i + j elements. We want the left part to hold half = (m + n + 1) / 2 elements (the +1 puts the extra element on the left for odd totals), so once we pick i, the cut j = half - i is forced. That reduces a two-dimensional search to a one-dimensional binary search over i.

Search the smaller array. We binary search i in [0, m] after swapping so that A is the shorter array. This bounds the work at O(log(min(m, n))) and keeps j = half - i within [0, n] (guaranteed when m <= n).

The four border values. Around the cut sit Aleft = A[i-1], Aright = A[i], Bleft = B[j-1], Bright = B[j]. When a cut lands at the very start (i == 0) there is no left element, so we treat Aleft = -∞; at the end (i == m) there is no right element, so Aright = +∞; likewise for B. These sentinels are the trick that erases every empty-partition edge case — no special branches for empty arrays or cuts at the boundary.

The validity condition. Because each array is individually sorted, Aleft <= Aright and Bleft <= Bright automatically. The cut is the correct global split exactly when the cross conditions also hold: Aleft <= Bright and Bleft <= Aright. That means every element on the left (the max of which is max(Aleft, Bleft)) is ≤ every element on the right (the min of which is min(Aright, Bright)).

Driving the search. If Aleft > Bright, we took too many large elements from A into the left — move the A-cut left: hi = i - 1. If instead Bleft > Aright (the only other failure), the A-cut is too far left — move it right: lo = i + 1. Otherwise we've found the cut.

Reading off the median. With a valid cut: if m + n is odd, the left side has the extra element, so the median is max(Aleft, Bleft). If even, it's the average of the two central values: (max(Aleft, Bleft) + min(Aright, Bright)) / 2. The (m + n + 1) / 2 choice of half is what makes the odd case this clean.

Why it terminates correctly. The window [lo, hi] on i strictly shrinks each iteration, and a valid partition always exists, so the loop returns from inside on the correct cut.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums1 = [1, 3], nums2 = [2] (A is the shorter, m=1 after swap → A=[2], B=[1,3])

Array state

i=0, j=2

Aleft=-∞, Aright=2, Bleft=3, Bright=+∞. Bleft(3) > Aright(2) → move A-cut right

i ↓

[0]

Current pointerResolved stateNot processed

Final result2.0

C · Code with teaching comments

solution.javaJava

Binary Search the Partition (Optimal) — optimal

11 teaching notes

1
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
2
    // Recurse with arguments swapped so we always binary search the SHORTER array →
3
    // O(log(min(m,n))).
4
    if (nums1.length > nums2.length) {
5
        return findMedianSortedArrays(nums2, nums1);
6
    }
7
    int m = nums1.length, n = nums2.length;
8
    // Left side gets the extra element on odd totals, making the odd median = max of
9
    // left borders.
10
    int half = (m + n + 1) / 2;
11
    int lo = 0, hi = m;
12
    while (lo <= hi) {
13
        // Cut position in the shorter array A.
14
        int i = lo + (hi - lo) / 2;
15
        // Cut in B is derived so left side always has exactly `half` elements.
16
        int j = half - i;
17
        // −∞ sentinel when A contributes nothing to the left — removes the empty-side
18
        // special case.
19
        int aLeft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
20
        // +∞ sentinel when the A-cut is at the end.
21
        int aRight = (i == m) ? Integer.MAX_VALUE : nums1[i];
22
        int bLeft  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
23
        int bRight = (j == n) ? Integer.MAX_VALUE : nums2[j];
24
        // Cross conditions = every left value ≤ every right value → correct partition.
25
        if (aLeft <= bRight && bLeft <= aRight) {
26
            if ((m + n) % 2 == 1) {
27
                // Odd total: median is the largest element of the left side.
28
                return Math.max(aLeft, bLeft);
29
            }
30
            // Even total: average the two central values.
31
            return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
32
        // Too many large A-values on the left → shift the A-cut left.
33
        } else if (aLeft > bRight) {
34
            hi = i - 1;
35
        } else {
36
            // Otherwise bLeft > aRight → A-cut too far left, shift right.
37
            lo = i + 1;
38
        }
39
    }
40
    throw new IllegalArgumentException("Input arrays are not sorted");
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(log(min(m, n))) timeO(1) spaceOpen the invariant and proofExplore the proof

The reframing — from 'merge and index' to 'find the balancing cut' — is the transferable idea. Deriving one cut from the other collapses the search to one dimension, and the ±∞ sentinels turn a notoriously edge-case-heavy problem into a handful of clean comparisons. The same partition-search mindset solves the generalised 'k-th element of two sorted arrays' and median-of-streams variants.

ComplexityO(log(min(m, n))) time, O(1) space — Binary search over the cut position in the smaller array (length min(m, n)) → log₂(min(m, n)) iterations, O(1) work each. No extra memory beyond a few variables.

E · Edge cases and pitfalls8nums1 = [], nums2 = [1] — m=0 → only i=0 possible; Aleft=-∞, Aright=+∞; median reads from B's borders → 1.0.Explore edge cases

Edge cases handled

nums1 = [], nums2 = [1]m=0 → only i=0 possible; Aleft=-∞, Aright=+∞; median reads from B's borders → 1.0.
nums1 = [1, 2], nums2 = [3, 4]Cut puts {1,2} | {3,4}; even total → (max(2,-∞... actually 2) + min(3,...)) → (2+3)/2 = 2.5.
nums1 = [3], nums2 = [-2, -1]After swap A=[3] is longer? n≥m enforced; sentinels handle all-negative values correctly.
all of A less than all of BCut lands at i=m or i=0 and sentinels make the cross conditions pass on the first valid position.

Pitfalls

Binary searching the larger array — gives O(log(max(m,n))) and can push j out of range.
Forgetting ±∞ sentinels — index-out-of-bounds on cuts at the boundary or empty arrays.
Using (m+n)/2 instead of (m+n+1)/2 for half — breaks the clean odd-median formula.
Integer division on the even-case average — must divide by 2.0 to keep the fractional median.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length, n = nums2.length;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int m = nums1.length, n = nums2.length;
    int half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;
        int j = half - i;
        int aLeft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int aRight = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int bLeft  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int bRight = (j == n) ? Integer.MAX_VALUE : nums2[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            if ((m + n) % 2 == 1) {
                return Math.max(aLeft, bLeft);
            }
            return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
        } else if (aLeft > bRight) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }
    throw new IllegalArgumentException("Input arrays are not sorted");
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Searching the longer array

Binary searching the larger array makes complexity O(log(max(m,n))) and lets the derived cut j = half - i fall outside [0, n], causing wrong borders or crashes. Always swap so the searched array is the shorter one.

Explore the code comparison

Don't write this

m, n = len(nums1), len(nums2)
# no swap — searches nums1 even if it is the longer array
half = (m + n + 1) // 2
lo, hi = 0, m

Write this instead

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
lo, hi = 0, m

Missing boundary sentinels

When a cut sits at index 0 or the array end, the missing border element must act as ±∞. Reading nums[i] or nums[i-1] directly throws an index error and breaks empty-array inputs.

Explore the code comparison

Don't write this

int aLeft = nums1[i - 1];   // crashes when i == 0
int aRight = nums1[i];      // crashes when i == m

Write this instead

int aLeft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int aRight = (i == m) ? Integer.MAX_VALUE : nums1[i];

Integer division in the even case

The median of an even-length total is generally a non-integer (e.g. 2.5). Dividing the sum of the two middle values by an integer 2 truncates the fraction.

Explore the code comparison

Don't write this

return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;

Write this instead

return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search the partition of the smaller array

Code pattern to memorize

ensure A is the shorter array
half = (m + n + 1) // 2
lo, hi = 0, m
while lo <= hi:
    i = (lo + hi) // 2          # cut in A
    j = half - i               # cut in B
    Aleft  = A[i-1] if i>0 else -inf;  Aright = A[i] if i<m else +inf
    Bleft  = B[j-1] if j>0 else -inf;  Bright = B[j] if j<n else +inf
    if Aleft <= Bright and Bleft <= Aright: # correct cut
        if (m+n) odd: return max(Aleft, Bleft)
        return (max(Aleft,Bleft) + min(Aright,Bright)) / 2
    elif Aleft > Bright: hi = i - 1
    else: lo = i + 1

Rules to remember

1Always binary search the smaller array so the range is [0, min(m, n)] → O(log(min(m, n))).
2The cut in B is derived: j = (m + n + 1) // 2 − i, so the left side always holds exactly half the elements.
3Guard the borders with ±∞ when a cut sits at index 0 or the array end — this removes every empty-side special case.
4Correct partition condition is Aleft ≤ Bright AND Bleft ≤ Aright; if Aleft > Bright move the A-cut left, else move it right.
5Use (m + n + 1) // 2 so the left side has the extra element on odd total — then the odd-median is max(Aleft, Bleft) with no extra arithmetic.

Use this pattern when

Median / k-th element across two (or more) sorted arrays in sub-linear time
Strict `O(log(m+n))` requirement that rules out merging
Any 'find the split that balances two sorted sequences' framing

Choose another pattern when

O(m + n) is acceptable → just merge with two pointers; far less error-prone
Arrays are unsorted → sort or use selection; binary-search partition needs sorted input
You need the full merged array, not just the median → merging is unavoidable

Interview takeaway

The leap is to stop thinking 'merge then index' and start thinking 'where do I cut?'. Binary searching a partition — with ±∞ sentinels erasing the edge cases — is the canonical O(log) technique for order-statistics across sorted inputs.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary search a partition for order statistics across sorted arrays. Recognise it when you need the median / k-th value of two sorted sequences in logarithmic time: derive one cut from the other, use ±∞ sentinels, and check the four border values. Generalises to the k-th element of two sorted arrays.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element in an Array
Coming soon
Order statistics on one array — quickselect averages O(n).
Kth Element of Two Sorted Arrays (generalisation)
Coming soon
Same partition idea but solve for an arbitrary k, discarding k/2 elements per step.
Find Median from Data Stream
Coming soon
Streaming median with two heaps instead of static sorted arrays.
Binary Search
The base template; this problem binary searches a cut rather than an element.

Same pattern

←

Koko Eating Bananas

Continue · Next problem

Find K-th Smallest Pair Distance

hardBinary SearchLC #4Frequently asked

Median of Two Sorted Arrays

LCPractice

Binary Search · 6 of 16 · 13 min

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)).

In plain English

Examples

Example 1

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Note: Merged = [1,2,3], odd length, median is the middle element 2.

Example 2

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Note: Merged = [1,2,3,4], even length, median = (2 + 3) / 2 = 2.5.

Example 3

Input: nums1 = [], nums2 = [1]
Output: 1.0
Note: One array empty; sentinels make the single element the median.

Constraints

nums1.length == m
nums2.length == n
0 ≤ m ≤ 1000
0 ≤ n ≤ 1000
1 ≤ m + n ≤ 2000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

Clarifying questions4First question: Can one of the arrays be empty?Explore questions

Q1.Can one of the arrays be empty?
Yes — m or n can be 0 (but not both). The ±∞ sentinels at the borders make an empty array behave correctly with no special-casing.
Q2.Is the total length odd or even — how does that change the answer?
Odd total → median is the single middle element (max of the two left borders). Even total → average of the two middle elements (max of left borders and min of right borders).
Q3.Do the arrays share values or have duplicates?
Both possible. The partition condition uses ≤, so equal border values still satisfy a valid cut.
Q4.Is O(m+n) acceptable, or must it be logarithmic?
The prompt insists on O(log(m+n)). I'll present the merge baseline for clarity, then deliver the O(log(min(m,n))) partition solution that meets the bound.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Binary searching the larger array (wrong complexity), mishandling the empty-partition borders (index out of bounds), or botching the odd/even median formula.

How to stand out

State the merge baseline and its O(m+n), then pivot to 'binary search the cut', explain the ±∞ sentinel trick that kills all the edge cases, and derive j from i so the left half size is fixed.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Merge (or Half-Merge) with Two Pointers — Baseline	`O(m + n)`	`O(1)`	Mention first to anchor correctness and the O(m+n) cost, then pivot to the logarithmic partition the prompt demands.	Read
2	Binary Search the Partition (Optimal)Optimal	`O(log(min(m, n)))`	`O(1)`	The answer they want. Frame it as 'binary search the cut in the smaller array' and emphasize the ±∞ sentinels.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Merge (or Half-Merge) with Two Pointers — Baseline

TimeO(m + n)SpaceO(1)

Mention first to anchor correctness and the O(m+n) cost, then pivot to the logarithmic partition the prompt demands.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you merged the two sorted arrays, where would the median sit?

2Hint 2Explore hint

You don't need the full merge — just advance two pointers until you've passed (m+n)/2 elements, tracking the middle one or two.

3Hint 3Explore hint

It's O(m+n) and trivially correct. Use it to sanity-check, but the prompt wants O(log(m+n)).

A · Core idea

Step two pointers through nums1 and nums2, always taking the smaller current element, until you've consumed (m + n) / 2 + 1 elements; remember the last one or two to form the median.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums1 = [1, 3], nums2 = [2]

take min(1,2)=1

count=1, advance nums1

Statelast = 1

Final result2.0

C · Code with teaching comments

solution.javaJava

Merge (or Half-Merge) with Two Pointers — Baseline — reference

3 teaching notes

1
public double findMedianSortedArrays(int[] a, int[] b) {
2
    int m = a.length, n = b.length, total = m + n;
3
    int i = 0, j = 0;
4
    int prev = 0, curr = 0;
5
    // Advance just past the middle — no need to merge the whole thing.
6
    for (int count = 0; count <= total / 2; count++) {
7
        prev = curr;
8
        // Pick the smaller head; the bounds checks handle an exhausted array.
9
        if (i < m && (j >= n || a[i] <= b[j])) {
10
            curr = a[i++];
11
        } else {
12
            curr = b[j++];
13
        }
14
    }
15
    if (total % 2 == 1) {
16
        return curr;
17
    }
18
    // Even total → average the two central elements.
19
    return (prev + curr) / 2.0;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m + n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(m + n) time, O(1) space — Walk both arrays once with two pointers, stopping at the middle — linear in the total length, constant memory.

E · Edge cases and pitfalls3O(m+n) — fails the asymptotic requirement even though it passes the tests.Explore edge cases

Pitfalls

O(m+n) — fails the asymptotic requirement even though it passes the tests.
Off-by-one on how many elements to consume for odd vs even totals.
Forgetting the j >= n / i < m guards when one array runs out.

03.2

Approach 2 of 2 · Optimal

Binary Search the Partition (Optimal)

TimeO(log(min(m, n)))SpaceO(1)

The answer they want. Frame it as 'binary search the cut in the smaller array' and emphasize the ±∞ sentinels.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Fix the total left-size to (m+n+1)/2. Then the cut position j in B is forced once you choose the cut i in A — so you only search i.

3Hint 3Explore hint

Search i in the SMALLER array. A cut is valid when Aleft ≤ Bright and Bleft ≤ Aright. If Aleft > Bright, your A-cut is too far right; otherwise too far left. Use ±∞ for out-of-range borders.

A · Core idea

Find, without merging, a partition that places exactly the lower half of all elements on the left.

Why it terminates correctly. The window [lo, hi] on i strictly shrinks each iteration, and a valid partition always exists, so the loop returns from inside on the correct cut.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums1 = [1, 3], nums2 = [2] (A is the shorter, m=1 after swap → A=[2], B=[1,3])

Array state

i=0, j=2

Aleft=-∞, Aright=2, Bleft=3, Bright=+∞. Bleft(3) > Aright(2) → move A-cut right

i ↓

[0]

Current pointerResolved stateNot processed

Final result2.0

C · Code with teaching comments

solution.javaJava

Binary Search the Partition (Optimal) — optimal

11 teaching notes

1
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
2
    // Recurse with arguments swapped so we always binary search the SHORTER array →
3
    // O(log(min(m,n))).
4
    if (nums1.length > nums2.length) {
5
        return findMedianSortedArrays(nums2, nums1);
6
    }
7
    int m = nums1.length, n = nums2.length;
8
    // Left side gets the extra element on odd totals, making the odd median = max of
9
    // left borders.
10
    int half = (m + n + 1) / 2;
11
    int lo = 0, hi = m;
12
    while (lo <= hi) {
13
        // Cut position in the shorter array A.
14
        int i = lo + (hi - lo) / 2;
15
        // Cut in B is derived so left side always has exactly `half` elements.
16
        int j = half - i;
17
        // −∞ sentinel when A contributes nothing to the left — removes the empty-side
18
        // special case.
19
        int aLeft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
20
        // +∞ sentinel when the A-cut is at the end.
21
        int aRight = (i == m) ? Integer.MAX_VALUE : nums1[i];
22
        int bLeft  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
23
        int bRight = (j == n) ? Integer.MAX_VALUE : nums2[j];
24
        // Cross conditions = every left value ≤ every right value → correct partition.
25
        if (aLeft <= bRight && bLeft <= aRight) {
26
            if ((m + n) % 2 == 1) {
27
                // Odd total: median is the largest element of the left side.
28
                return Math.max(aLeft, bLeft);
29
            }
30
            // Even total: average the two central values.
31
            return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
32
        // Too many large A-values on the left → shift the A-cut left.
33
        } else if (aLeft > bRight) {
34
            hi = i - 1;
35
        } else {
36
            // Otherwise bLeft > aRight → A-cut too far left, shift right.
37
            lo = i + 1;
38
        }
39
    }
40
    throw new IllegalArgumentException("Input arrays are not sorted");
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(log(min(m, n))) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8nums1 = [], nums2 = [1] — m=0 → only i=0 possible; Aleft=-∞, Aright=+∞; median reads from B's borders → 1.0.Explore edge cases

Edge cases handled

nums1 = [], nums2 = [1]m=0 → only i=0 possible; Aleft=-∞, Aright=+∞; median reads from B's borders → 1.0.
nums1 = [1, 2], nums2 = [3, 4]Cut puts {1,2} | {3,4}; even total → (max(2,-∞... actually 2) + min(3,...)) → (2+3)/2 = 2.5.
nums1 = [3], nums2 = [-2, -1]After swap A=[3] is longer? n≥m enforced; sentinels handle all-negative values correctly.
all of A less than all of BCut lands at i=m or i=0 and sentinels make the cross conditions pass on the first valid position.

Pitfalls

Binary searching the larger array — gives O(log(max(m,n))) and can push j out of range.
Forgetting ±∞ sentinels — index-out-of-bounds on cuts at the boundary or empty arrays.
Using (m+n)/2 instead of (m+n+1)/2 for half — breaks the clean odd-median formula.
Integer division on the even-case average — must divide by 2.0 to keep the fractional median.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Searching the longer array

Explore the code comparison

Don't write this

m, n = len(nums1), len(nums2)
# no swap — searches nums1 even if it is the longer array
half = (m + n + 1) // 2
lo, hi = 0, m

Write this instead

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
lo, hi = 0, m

Missing boundary sentinels

When a cut sits at index 0 or the array end, the missing border element must act as ±∞. Reading nums[i] or nums[i-1] directly throws an index error and breaks empty-array inputs.

Explore the code comparison

Don't write this

int aLeft = nums1[i - 1];   // crashes when i == 0
int aRight = nums1[i];      // crashes when i == m

Write this instead

int aLeft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int aRight = (i == m) ? Integer.MAX_VALUE : nums1[i];

Integer division in the even case

The median of an even-length total is generally a non-integer (e.g. 2.5). Dividing the sum of the two middle values by an integer 2 truncates the fraction.

Explore the code comparison

Don't write this

return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;

Write this instead

return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search the partition of the smaller array

Code pattern to memorize

ensure A is the shorter array
half = (m + n + 1) // 2
lo, hi = 0, m
while lo <= hi:
    i = (lo + hi) // 2          # cut in A
    j = half - i               # cut in B
    Aleft  = A[i-1] if i>0 else -inf;  Aright = A[i] if i<m else +inf
    Bleft  = B[j-1] if j>0 else -inf;  Bright = B[j] if j<n else +inf
    if Aleft <= Bright and Bleft <= Aright: # correct cut
        if (m+n) odd: return max(Aleft, Bleft)
        return (max(Aleft,Bleft) + min(Aright,Bright)) / 2
    elif Aleft > Bright: hi = i - 1
    else: lo = i + 1

Rules to remember

1Always binary search the smaller array so the range is [0, min(m, n)] → O(log(min(m, n))).
2The cut in B is derived: j = (m + n + 1) // 2 − i, so the left side always holds exactly half the elements.
3Guard the borders with ±∞ when a cut sits at index 0 or the array end — this removes every empty-side special case.
4Correct partition condition is Aleft ≤ Bright AND Bleft ≤ Aright; if Aleft > Bright move the A-cut left, else move it right.
5Use (m + n + 1) // 2 so the left side has the extra element on odd total — then the odd-median is max(Aleft, Bleft) with no extra arithmetic.

Use this pattern when

Median / k-th element across two (or more) sorted arrays in sub-linear time
Strict `O(log(m+n))` requirement that rules out merging
Any 'find the split that balances two sorted sequences' framing

Choose another pattern when

O(m + n) is acceptable → just merge with two pointers; far less error-prone
Arrays are unsorted → sort or use selection; binary-search partition needs sorted input
You need the full merged array, not just the median → merging is unavoidable

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element in an Array
Coming soon
Order statistics on one array — quickselect averages O(n).
Kth Element of Two Sorted Arrays (generalisation)
Coming soon
Same partition idea but solve for an arbitrary k, discarding k/2 elements per step.
Find Median from Data Stream
Coming soon
Streaming median with two heaps instead of static sorted arrays.
Binary Search
The base template; this problem binary searches a cut rather than an element.

Same pattern

←

Koko Eating Bananas

Continue · Next problem

Find K-th Smallest Pair Distance