LeetCode 4 Median of Two Sorted Arrays: The Binary Search Partition, Explained Slowly

LeetCode 4 has a reputation as the hardest problem on most interview lists, and the usual explanations don't help: they jump straight to four variables named maxLeftX, minRightY and so on, and you end up memorising index arithmetic you can't rebuild under pressure. This page goes the other way. It starts from what a median is, turns that into one picture, and derives every line of the code from that picture. If you can redraw the picture, you can rewrite the solution.

We'll also cover the linear solutions you should mention first, three dry runs that exercise every branch, code in Python, C++ and Java, and the k-th element method, which solves a more general problem. If binary search itself feels shaky, the binary search patterns guide is a good warm-up.

The Problem: Median of Two Sorted Arrays

Given two sorted arrays nums1 (size m) and nums2 (size n), return the median of the two sorted arrays combined. The overall run time should be O(log(m + n)).

Constraints: 0 ≤ m, n ≤ 1000, 1 ≤ m + n ≤ 2000, values between −10⁶ and 10⁶. So one array can be empty but not both, and the values are small enough that sums never overflow a 32-bit integer. Note the return type is a floating-point number.

Recall the definition: for an odd count, the median is the middle element; for an even count, it's the average of the two middle elements.

O(m + n) Solutions You Should Mention First

Merge and pick the middle

Merge the two arrays like the merge step of merge sort, then read the middle. O(m + n) time and space. It's correct and passes on LeetCode because the arrays are small, but it ignores the stated complexity requirement.

Walk to the middle with two pointers

You don't need the merged array, only the elements at positions (m+n−1)/2 and (m+n)/2. Advance two pointers like a merge, counting steps, and remember the last two values. O(m + n) time, O(1) space.

def median_two_pointers(A, B):
    m, n = len(A), len(B)
    total = m + n
    i = j = 0
    prev = cur = 0
    for _ in range(total // 2 + 1):        # step to index total // 2
        prev = cur
        if i < m and (j >= n or A[i] <= B[j]):
            cur = A[i]
            i += 1
        else:
            cur = B[j]
            j += 1
    return float(cur) if total % 2 else (prev + cur) / 2

In an interview, say this version in one or two sentences, note that it's O(m + n), then say: "Since both arrays are sorted and we only need a position, I think we can binary search." That framing tells the interviewer you know where you're going. For more on this style of pointer walk, see two pointers technique problems.

The Partition Intuition, Step by Step

Step 1: what a median really does

Forget averages for a moment. A median cuts a sorted list into two halves of equal size (the left half gets one extra element when the count is odd), and everything on the left is ≤ everything on the right. Once you have such a cut, the median is either the largest element on the left (odd count) or the average of the largest on the left and the smallest on the right (even count).

Step 2: a cut of the combined array is a pair of cuts

Here's the key move. Any cut of the combined sorted array corresponds to cutting A somewhere and cutting B somewhere. The left half of the combined array is "the left part of A" plus "the left part of B".

Step 3: the size condition fixes j once you pick i

We need the left half to contain half = (m + n + 1) / 2 elements (integer division). So i + j = half, which means j = half − i. We only have one free variable, i, which can range from 0 (take nothing from A) to m (take all of A).

Why (m + n + 1) / 2? For odd totals, the +1 gives the extra element to the left, so the median is just the left maximum. For even totals, the +1 disappears in integer division, so both halves are equal. One formula covers both cases.

Step 4: the order condition only needs two comparisons

We need every left element ≤ every right element. Within A, the left part is already ≤ the right part because A is sorted. Same for B. So the only comparisons that can fail are the ones that cross arrays:

If both hold, the cut is the median cut. Only the boundary elements matter, because they're the largest on the left and smallest on the right within each array.

Step 5: when a check fails, you know which way to move

• If A[i−1] > B[j]: we took too many elements from A (one of A's left elements is too big to be on the left). Decrease i. As i goes down, j goes up, which is also the right direction for B.
• If B[j−1] > A[i]: we took too few from A. Increase i.

Both checks can't fail at the same time. If they did, we'd have A[i−1] > B[j] ≥ B[j−1] > A[i], so A[i−1] > A[i], contradicting that A is sorted. So the direction is always unambiguous, and the "is this cut too far right?" property is monotonic in i. Monotonic yes/no over a range is exactly what binary search needs.

Binary Searching the Cut

Why search over the shorter array

Let A be the shorter array, so m ≤ n. For every i in [0, m], we need j = half − i to be a valid cut of B, i.e. 0 ≤ j ≤ n.

• Largest j is at i = 0: j = half = (m+n+1)/2 ≤ (2n+1)/2 = n. Valid.
• Smallest j is at i = m: j = half − m ≥ (2m+1)/2 − m = 0. Valid.

If you search the longer array instead, j can go negative and you'll index out of bounds. Swapping so A is shorter is not an optimisation; it's what makes the index arithmetic safe. As a bonus, the search costs O(log min(m, n)), which is within the required O(log(m + n)).

Handling empty sides with sentinels

When i = 0, A contributes nothing to the left, so there is no A[i−1]. When i = m, there is no A[i]. Same for j. Define:

• Missing left boundary → −∞ (so "left ≤ anything" is always true).
• Missing right boundary → +∞ (so "anything ≤ right" is always true).

With these four values, the same two comparisons work at every cut, including the edges, with no special cases.

The algorithm

1. If A is longer than B, swap them. Set lo = 0, hi = m (inclusive; i = m is a valid cut), half = (m + n + 1) / 2.
2. While lo ≤ hi: i = (lo + hi) / 2, j = half − i. Read Aleft, Aright, Bleft, Bright with sentinels.
3. If Aleft ≤ Bright and Bleft ≤ Aright: found the cut. Return max(Aleft, Bleft) if the total is odd, else (max(Aleft, Bleft) + min(Aright, Bright)) / 2.
4. Else if Aleft > Bright: hi = i − 1. Else lo = i + 1.

For sorted inputs the loop always finds a valid cut before lo passes hi, since a median cut always exists.

Three Dry Runs

Dry run 1: odd total, lo moves right

A = [1, 3, 8, 9, 15] (m = 5), B = [7, 11, 18, 19, 21, 25] (n = 6). Combined: 1 3 7 8 9 11 15 18 19 21 25, so the median is 11. half = (5 + 6 + 1) / 2 = 6.

Total is odd, so the median is max(9, 11) = 11. Left half: {1, 3, 8, 9} from A plus {7, 11} from B: six elements, all ≤ every element of {15} ∪ {18, 19, 21, 25}.

Dry run 2: even total, cut at the end of A

A = [1, 2], B = [3, 4]. half = (2 + 2 + 1) / 2 = 2.

Even total: (max(2, −∞) + min(+∞, 3)) / 2 = (2 + 3) / 2 = 2.5. This run shows why hi must start at m and not m − 1: the correct cut takes all of A.

Dry run 3: hi moves left, cut at the start of A

A = [4, 5, 6], B = [1, 2, 3]. half = 3.

Median: (max(−∞, 3) + min(4, +∞)) / 2 = 3.5. Between them, these three runs hit both move directions and all four sentinel positions.

Code in Python, C++ and Java

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A                       # binary search the shorter array
        m, n = len(A), len(B)
        half = (m + n + 1) // 2
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            a_left = A[i - 1] if i > 0 else float('-inf')
            a_right = A[i] if i < m else float('inf')
            b_left = B[j - 1] if j > 0 else float('-inf')
            b_right = B[j] if j < n else float('inf')

            if a_left <= b_right and b_left <= a_right:
                if (m + n) % 2 == 1:
                    return float(max(a_left, b_left))
                return (max(a_left, b_left) + min(a_right, b_right)) / 2
            if a_left > b_right:
                hi = i - 1                    # took too many from A
            else:
                lo = i + 1                    # took too few from A
        raise ValueError("input arrays must be sorted")

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        const vector<int>& A = nums1;
        const vector<int>& B = nums2;
        int m = A.size(), n = B.size();
        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) ? A[i - 1] : INT_MIN;
            int aRight = (i < m) ? A[i]     : INT_MAX;
            int bLeft  = (j > 0) ? B[j - 1] : INT_MIN;
            int bRight = (j < n) ? B[j]     : INT_MAX;

            if (aLeft <= bRight && bLeft <= aRight) {
                if ((m + n) % 2 == 1) return max(aLeft, bLeft);
                return (static_cast<double>(max(aLeft, bLeft)) + min(aRight, bRight)) / 2.0;
            }
            if (aLeft > bRight) hi = i - 1;
            else lo = i + 1;
        }
        return 0.0;   // unreachable for sorted input
    }
};

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int[] A = nums1, B = nums2;
        int m = A.length, n = B.length;
        int half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) >>> 1;
            int j = half - i;
            int aLeft  = (i > 0) ? A[i - 1] : Integer.MIN_VALUE;
            int aRight = (i < m) ? A[i]     : Integer.MAX_VALUE;
            int bLeft  = (j > 0) ? B[j - 1] : Integer.MIN_VALUE;
            int bRight = (j < n) ? B[j]     : Integer.MAX_VALUE;

            if (aLeft <= bRight && bLeft <= aRight) {
                if (((m + n) & 1) == 1) return Math.max(aLeft, bLeft);
                return ((double) Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
            }
            if (aLeft > bRight) hi = i - 1;
            else lo = i + 1;
        }
        throw new IllegalArgumentException("input arrays must be sorted");
    }
}

Why INT_MIN / INT_MAX sentinels are safe here

Using the integer limits as ±∞ works because the values are bounded by ±10⁶, so no real value equals a sentinel. Also, in the even case the left half has at least one real element and so does the right half (each has (m+n)/2 ≥ 1 elements), so max(left) and min(right) are always real values. A sentinel never ends up in the average. Casting to double before adding is still a good habit: if the inputs were near the int limits, the sum of two real values could overflow.

Complexity

For the arrays on LeetCode (m ≤ 1000), the partition search finishes in at most about 11 iterations. The C++ version recurses once to swap arguments, which adds a single stack frame, not a log factor. The Big O guide explains why log(min(m, n)) ⊆ O(log(m + n)).

Edge Cases and Common Bugs

Alternative: Find the k-th Smallest of Two Sorted Arrays

A second classic approach solves a more general question: the k-th smallest element across both arrays. The median is then the k-th element for k = (m+n+1)/2, averaged with the next one for even totals.

The idea: look at the element at position k/2 in each array (or the last element if the array is shorter). Suppose A[k/2 − 1] ≤ B[k/2 − 1]. Count how many elements can come before A[k/2 − 1] in the merged order: at most the k/2 − 1 elements of A in front of it, plus at most the k/2 − 1 elements of B in front of B[k/2 − 1]. So A[k/2 − 1] sits at rank k − 1 or lower, and so does every element before it in A. None of A's first k/2 elements can be the k-th smallest. Discard them and look for the (k − k/2)-th element in what's left.

def kth_smallest(A, B, k):
    i = j = 0                                   # start of the remaining part of A and B
    while True:
        if i == len(A):
            return B[j + k - 1]
        if j == len(B):
            return A[i + k - 1]
        if k == 1:
            return min(A[i], B[j])
        step = k // 2
        ni = min(i + step, len(A)) - 1          # candidate index in A
        nj = min(j + step, len(B)) - 1          # candidate index in B
        if A[ni] <= B[nj]:
            k -= ni - i + 1                     # discard A[i..ni]
            i = ni + 1
        else:
            k -= nj - j + 1                     # discard B[j..nj]
            j = nj + 1

def median_via_kth(A, B):
    total = len(A) + len(B)
    if total % 2:
        return float(kth_smallest(A, B, total // 2 + 1))
    return (kth_smallest(A, B, total // 2) + kth_smallest(A, B, total // 2 + 1)) / 2

Each iteration discards at least one element and roughly half of the remaining k, so it runs in O(log k) = O(log(m + n)). It's often easier to explain than the partition method and it answers the follow-up "what about the k-th element, not just the median?" directly. The trade-off: the median needs two calls in the even case, and the "why can we discard these" argument has to be stated carefully.

Which one should you present?

Present whichever you can explain without hesitation. Most interviewers accept either; what they reject is code you can't justify.

How This Problem Shows Up in Interviews

LeetCode 4 is commonly reported in Google, Amazon and Microsoft loops, and it appears in Indian product-company rounds mostly for senior or competitive-programming-heavy roles. Because it's famous, interviewers care much more about your reasoning than whether you reach the answer.

A presentation that works

1. Clarify: Can either array be empty? Are there duplicates? Return type is double?
2. Baseline: "Merging is O(m + n). Walking two pointers to the middle is O(m + n) time and O(1) space."
3. Reframe: "The median is a cut where the left half has (m+n+1)/2 elements and every left value ≤ every right value. If I take i from A, I must take half − i from B."
4. Derive the checks: only the two cross comparisons can fail, and they tell me which way to move. That's monotonic, so binary search.
5. Code it with sentinels, then dry run the [1, 2] / [3, 4] case where the cut lands at the edge.
6. State complexity and why the search is over the shorter array.

Follow-ups to prepare for

• "Find the k-th smallest element." The k-th element method above.
• "What if there are K sorted arrays?" Binary search on the answer value: for a candidate x, count elements ≤ x in each array with binary search, O(K log n) per check, times O(log range) checks. Or a heap-based k-way merge to position k.
• "Median of a row-wise sorted matrix." Same value-space binary search.
• "Numbers arrive as a stream; report the median after each." Different problem: two heaps (LeetCode 295), covered in the heap and priority queue guide.
• "What if the arrays don't fit in memory but support random access?" The partition method still works, needing only O(log n) reads, which is a nice point about why logarithmic algorithms matter on disk.

If you understand the cut picture, you've also understood a reusable idea: binary search over a split point, where one variable determines the other. It shows up again in problems like the k-th smallest pair and splitting arrays, and in the selection problems discussed in Kth Largest Element. That's the real return on the time you spend on this one.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.