4.11.7 — Median of Two Sorted Arrays

LeetCode 4 · Hard

The problem

Two sorted arrays. Find the median of their combined contents, in O(\log(m+n)).

nums1 = [1,3], nums2 = [2]        →  2.0      (merged: [1,2,3])
nums1 = [1,2], nums2 = [3,4]      →  2.5      (merged: [1,2,3,4])

To put this in plain English: you are given two arrays that are individually sorted. If you were to combine them into one massive sorted array, what would be the number in the exact middle? If the combined size is even, take the average of the two middle numbers.

Constraints to Keep in Mind:

• nums1.length == m, nums2.length == n
• 0 <= m <= 1000, 0 <= n <= 1000
• 1 <= m + n <= 2000 (Both won't be empty at the same time)
• -10^6 <= nums1[i], nums2[i] <= 10^6

The Brute Force Approach

The simplest idea is just to merge the two arrays.

• How it works: You can create a new array merged and use two pointers (like in Merge Sort) to combine nums1 and nums2 into a single sorted list. Then, depending on whether the total length is odd or even, you return the middle element or the average of the two middle elements.
• Why it's too slow: Creating and filling a new array takes O(m + n) time and O(m + n) extra space. Alternatively, you could just keep track of the middle elements without storing the full merged array, reducing space to O(1), but the time is still O(m + n). The problem explicitly rules this out and demands O(\log(m+n)), meaning we must use binary search.

The pattern

The median splits the combined data into two halves of equal size, where everything in the left half is at most everything in the right half. So instead of finding a value, find the cut.

Draw a vertical line through both arrays at once:

A:  a0  a1  a2 | a3  a4
B:  b0  b1     | b2  b3  b4
    └── left ──┘└── right ──┘

Take i elements from the front of A and j from the front of B. If you want a total of half elements on the left, then j is forced:

j = \text{half} - i

That is the first key idea. You only choose i. The value of j follows, so there is one dimension to search, not two.

The second key idea is the condition for a correct cut. Everything on the left must be at most everything on the right. Within each array that is automatic, since both are sorted. What has to be checked is the two cross comparisons:

A_{\text{left}} \le B_{\text{right}} \quad\text{and}\quad B_{\text{left}} \le A_{\text{right}}

where A_left is the last element taken from A, A_right the first element left behind, and likewise for B.

If both hold, the cut is correct and the median is right there at the boundary. If A_left > B_right, you took too much from A, so move the cut left. If B_left > A_right, you took too little, so move right.

That is a monotonic condition, so binary search i.

Three details that make it work

Binary search the shorter array. Then j = half - i can never fall outside B's bounds. Search the longer one and j can go negative or past the end, and you spend the rest of your life adding guards.

Use the fence model. The cut can be anywhere from "take nothing from A" to "take all of A", which is len(A) + 1 positions for an array of length len(A). So low = 0 and high = len(A), one past the last index. Report 4 named this the fence model — you are choosing a gap between elements, not an element.

Picture a fence between posts. The elements are post slots; the fence is what goes between them. An array of length 5 has six places to put a fence — before the first element, between each pair, or after the last:

  fence positions:   0    1    2    3    4    5
                     |    |    |    |    |    |
  array slots:     [ a0 , a1 , a2 , a3 , a4 ]
                     |    |    |    |    |    |
                  fence  fence  ...            fence
                  here   here                  here

When you set i = 2, you are dropping the fence at position 2. That means two elements go to the left (a0, a1) and the rest go to the right (a2, a3, a4). No element is "the fence" — the fence lives in the gap between a1 and a2.

Now here is the part that trips people up: what does i actually point at in array-index terms?

• i is the starting index of the right side. When the fence is at position 2, the right side starts at A[2], which is a2. So A_right = A[i].
• i - 1 is the last index of the left side. The left side ends at A[1], which is a1. So A_left = A[i - 1].

Think of i as answering the question "how many elements did I take?" If you took 2, then indices 0 and 1 are on the left (that's i - 1 = 1 at the boundary) and index 2 onward is on the right (that's i = 2 at the boundary). The fence sits in the gap between index i - 1 and index i.

The edge cases follow naturally. i = 0 means "take nothing from A" — there is no A[i - 1], so A_left is -\infty. i = len(A) means "take everything from A" — there is no A[i], so A_right is +\infty.

The same logic applies to B with j: B_left = B[j - 1] and B_right = B[j].

Use infinities at the edges. If i == 0 nothing was taken from A, so A_left should never block the comparison — set it to -\infty. If i == len(A) nothing is left behind, so A_right is +\infty. This removes every boundary branch, and it is the trick that turns a mess of if statements into four clean lines.

Getting the halves right

Let total = m + n and half = (total + 1) // 2.

The + 1 rounds up, which means that when the total is odd, the left side gets the extra element and the median is the largest value on the left. When the total is even, the two sides are equal and the median is the average of the largest on the left and the smallest on the right.

Doing it this way means one formula covers both cases with a single if at the end.

Why the median always lands on the left for odd totals

This is the part that feels wrong until you see it on paper. You might think: "i is the first index of the right side, so isn't the median on the right?" No. The variable i is a count of how many elements you took, and the formula half = (total + 1) // 2 is what makes the median land on the left. Let's trace it.

Odd example — 5 elements total. half = (5 + 1) // 2 = 3. The left side gets 3 elements, the right side gets 2. The median of 5 elements is the 3rd one (position 2 in zero-indexed terms), which is the last element of the left partition — the biggest thing on the left.

merged (sorted):  [ 1,  2,  3,  4,  5 ]
                    ─────────  ──────
                     left (3)   right (2)
                          ↑
                     3rd element = median
                     = max of left side

The 3rd element is max(A_left, B_left) — whichever array contributed the last (largest) element to the left partition.

Even example — 6 elements total. half = (6 + 1) // 2 = 3. The left gets 3, the right gets 3. The median is the average of the 3rd and 4th elements, which is (max of left + min of right) / 2.

merged (sorted):  [ 1,  2,  3,  4,  5,  6 ]
                    ─────────  ──────────
                     left (3)    right (3)
                          ↑  ↑
                        3rd  4th  → median = (3 + 4) / 2

The mental model: half = (total + 1) // 2 is a deliberate choice to make the left partition one element fatter when the total is odd. That single extra element is the median. You don't need to look at the right side at all — the median is the biggest value sitting on the left, which is max(A_left, B_left).

But wait — i is an index into the right side, right? Yes, A[i] is the first element on the right. That doesn't matter. What matters is that A[i - 1] — the element just before the fence — is on the left. The fence counts how many you took, and half made you take one more than the other side. So the extra element (the median) ended up on the left, sitting at position i - 1 in one of the two arrays. You just don't know which array contributed it, so you take max(A_left, B_left) to find the larger of the two left-side boundary elements — and that is the median.

The solution

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
        total = len(A) + len(B)
        half = (total + 1) // 2

        low, high = 0, len(A)                  # fence model

        while low <= high:
            i = low + (high - low) // 2        # take i from A
            j = half - i                       # so j from B is forced

            A_left  = A[i - 1] if i > 0        else float('-inf')
            A_right = A[i]     if i < len(A)   else float('inf')
            B_left  = B[j - 1] if j > 0        else float('-inf')
            B_right = B[j]     if j < len(B)   else float('inf')

            if A_left <= B_right and B_left <= A_right:        # correct cut
                if total % 2:
                    return float(max(A_left, B_left))
                return (max(A_left, B_left) + min(A_right, B_right)) / 2

            if A_left > B_right:
                high = i - 1                   # took too much from A
            else:
                low = i + 1                    # took too little

        return 0.0

TypeScript

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  const [A, B] = nums1.length <= nums2.length ? [nums1, nums2] : [nums2, nums1];
  const total = A.length + B.length;
  const half = Math.floor((total + 1) / 2);

  let low = 0, high = A.length;

  while (low <= high) {
    const i = low + Math.floor((high - low) / 2);
    const j = half - i;

    const aLeft  = i > 0 ? A[i - 1] : -Infinity;
    const aRight = i < A.length ? A[i] : Infinity;
    const bLeft  = j > 0 ? B[j - 1] : -Infinity;
    const bRight = j < B.length ? B[j] : Infinity;

    if (aLeft <= bRight && bLeft <= aRight) {
      if (total % 2) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }

    if (aLeft > bRight) high = i - 1;
    else low = i + 1;
  }

  return 0.0;
}

Code Walkthrough

1. A, B = ...: We enforce that A is the shorter array. If B were shorter, calculating j = half - i might result in an out-of-bounds index for B.
2. total = len(A) + len(B), half = (total + 1) // 2: Calculate the combined size and exactly how many elements need to be placed in the left partition.
3. while low <= high:: Standard binary search loop over the shorter array A.
4. i = low + (high - low) // 2: We decide to take i elements from the front of A.
5. j = half - i: Because the left partition must always have exactly half elements, we take the remaining j elements from B.
6. A_left, A_right, B_left, B_right: We fetch the four elements around our two cuts. If a cut is at the absolute boundary (index 0 or max length), we substitute -inf or inf so that comparisons don't crash.
7. if A_left <= B_right and B_left <= A_right:: The AHA condition. The cut is completely valid. If the combined array length is odd, the median is just the biggest number we put on the left side: max(A_left, B_left). If even, it's the average of the biggest on the left and smallest on the right.
8. if A_left > B_right:: We took too many elements from A because an element on A's left side is bigger than an element on B's right side. Move A's cut to the left: high = i - 1.
9. else:: We took too few elements from A. Move A's cut to the right: low = i + 1.

Trace

A = [1, 3], B = [2]. A is already the shorter, total = 3, half = 2.

low	high	i	j	A_left	A_right	B_left	B_right	verdict
0	2	1	1	1	3	2	∞	1 ≤ ∞ ✓ and 2 ≤ 3 ✓ — correct cut

Total is odd, so the median is max(A_left, B_left) = max(1, 2) = 2. ✓

The cut takes [1] from A and [2] from B on the left, leaving [3] on the right. The merged array is [1, 2, 3] and the median is 2.

Complexity

• Time Complexity: O(\log(\min(m, n))). By ensuring A is the shorter array, our search space is the length of A, which is \min(m, n). Binary searching this range takes \log(\min(m, n)) steps. Inside the loop, all operations (indexing, comparing) are O(1). This strictly satisfies and actually beats the required O(\log(m+n)) bound.
• Space Complexity: O(1) extra space. We only store a few pointer and value variables (low, high, i, j, A_left, etc.). We never actually build the merged array.

Being realistic about this problem

This is the hardest binary search commonly asked, and getting it perfect under pressure is unusual. Have a plan for partial credit.

Say the merge solution first: O(m+n), obviously correct, and it establishes that you understand the question. Then describe the cut idea in words — "the median is a cut where everything on the left is at most everything on the right, and choosing how much to take from one array forces the other" — even if the code does not come out perfectly. That description is most of the marks.

Where this goes next

• Kth Smallest Element in Two Sorted Arrays — the same cut with half replaced by k. This problem is the special case k = (m+n+1)/2, which is a good way to remember it.
• Kth Smallest in a Sorted Matrix — binary search on the value, counting how many entries fall below it. A different technique for a similar-sounding question, and worth contrasting.
• Merging in general — the fence idea appears in external sorting and in parallel merge algorithms, where two threads must be given equal work without merging first.

What the interviewer will push on

"Why does j follow from i?" The left side must hold exactly half elements, so j = half - i.

"Why search the shorter array?" So that j always stays inside B's bounds.

"Why the infinities?" They make the boundary cases obey the same comparison as everything else, removing four branches.

"Why (total + 1) // 2?" It gives the extra element to the left side when the total is odd, so one formula covers both parities.

"Can you do it in O(m+n)?" Yes, by merging — and say that first, before attempting this.

One thing to volunteer: state the two laws before writing code. "The size law fixes j once I choose i; the ordering law is the two cross comparisons." Naming them is what turns this from a memorised trick into a derivation.

Next: 4.12 goes back to first principles on recursion — what the machine is doing, how to write a recurrence you can trust, and why backtracking is depth-first search over a tree you never build.