Median of Two Sorted Arrays

Problem in Plain English

Given two sorted arrays, return the median of their combined elements without merging them. Binary searching the split point in the smaller array balances both halves and reads the median off the four border values.

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The median is the middle value of the merged order, or the average of the two middle values when the combined length is even. The overall run time complexity should be $O(log(m + n))$ , which rules out merging both arrays.

Constraints

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

Examples

Example 1

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

The merged array is [1, 2, 3] and its middle value is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000

The merged array is [1, 2, 3, 4] and the median is (2 + 3) / 2 = 2.5.

Example 3

Input: nums1 = [], nums2 = [7]
Output: 7.00000

One input is empty and the combined length is the minimum allowed, one. The only element is 7, so it is the median; the empty input contributes no actual border values.

Example 4

Input: nums1 = [-1000000,2,2], nums2 = [2,1000000,1000000]
Output: 2.00000

The combined order is [-1000000, 2, 2, 2, 1000000, 1000000]. Positions 2 and 3 both contain 2, so their average is 2. Equal border values form a valid cut, even with negative and maximum-bound values elsewhere.

Intuition

A median separates the smaller half of the values from the larger half. A partition is a cut between elements, and its position counts how many elements are on the left. For [1, 3] and [2], cuts after 1 and 2 give a left half containing [1, 2] and a right half containing [3]. The left half holds one extra element for an odd total, so its largest value, 2, is the median. Sorted inputs let us verify a cut using only the values beside it instead of building the full merged order.

Approaches

Merge Then Median

Solution Details

Reveal Merge Then Median: intuition, complexity, and code

Intuition

Merging two sorted arrays with the two-pointer walk produces the fully sorted combined order, from which the median is read directly. This is correct because the merge preserves order and the median is defined on exactly that order.

Step-by-Step Logic

Start pointers i = 0 and j = 0 and an empty merged sequence. Each pointer identifies the next unconsumed value of its array; Example 1 starts with 1 and 2.
While both inputs have values remaining, append the smaller current value and advance only its pointer. On equality, take the second input. Example 1 appends 1 and then 2, leaving i = 1, j = 1.
Once one input is exhausted, append every remaining value from the other in order. Example 1 appends the remaining 3, producing [1, 2, 3].
Let total = m + n. For an odd total return the value at index total // 2; Example 1 returns index 1, value 2.
For an even total, average the values at indices total // 2 - 1 and total // 2 using floating-point division. This baseline is correct but does not meet the required logarithmic time.

Why It Works

Before each append, the merged sequence contains exactly the values already consumed, in sorted order. The smallest remaining value must be at the front of one of the two sorted suffixes, so choosing the smaller front preserves this invariant. When one suffix is empty, the other is already sorted and can be copied directly. At termination every input element appears exactly once. Reading the middle one or two positions of that complete sorted sequence therefore returns the median by definition.

Dry Run

Merge Then Median: variable states at each step
Action	`i` before -> after	`j` before -> after	Merged values after action
Initialize	`0`	`0`	`[]`
Compare `1 < 2`; append `1`	`0 -> 1`	`0 -> 0`	`[1]`
Compare `3 < 2` is false; append `2`	`1 -> 1`	`0 -> 1`	`[1, 2]`
Second input exhausted; append remaining `3`	`1 -> 2`	`1 -> 1`	`[1, 2, 3]`
Both inputs consumed; `total = 3` is odd	`2`	`1`	middle index `1`; return `2.00000`

Complexity Analysis

Time Complexity

O(m + n)

Space Complexity

O(m + n)

Let m and n be the input lengths. Each of the m + n values is copied once, so the merge takes linear time and the stored merged sequence takes O(m + n) auxiliary space. Python also creates temporary suffix slices for extend; their total size is at most m + n and does not change the space bound. The returned scalar is constant space, and inputs are unchanged. At the stated value bounds, adding two middle values stays within [-2000000, 2000000], safely inside Java int and exact in JavaScript Number.

Code

Solution.java

1class Solution {2    public double findMedianSortedArrays(int[] nums1, int[] nums2) {3        int m = nums1.length, n = nums2.length;4        int[] merged = new int[m + n];5        int i = 0, j = 0, k = 0;6        while (i < m && j < n) {7            if (nums1[i] < nums2[j]) {8                merged[k++] = nums1[i++];9            } else {10                merged[k++] = nums2[j++];11            }12        }13        while (i < m) {14            merged[k++] = nums1[i++];15        }16        while (j < n) {17            merged[k++] = nums2[j++];18        }19        int total = m + n;20        if (total % 2 == 1) {21            return merged[total / 2];22        }23        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;24    }25}

Hints

Hint 1

The median only needs the middle one or two values, not the whole merged order.

Hint 2

Imagine cutting both arrays so the left pieces together hold half the elements; the cut in one array fixes the cut in the other.

Hint 3

Binary search the cut in the smaller array until every left border is at or below every right border.

Edge Cases

Either input can be empty: [] and [7] return 7, while [] and [1, 2] return 1.5. Both empty is excluded by the combined-length constraint.
All values of one array below all of the other push the split to an extreme end of the smaller array.
Even and odd combined lengths read the answer differently: average of middle borders versus largest left border.
Highly unbalanced lengths work because the longer-array cut is derived from the shorter-array cut; swapping roles does not change the median.
Duplicate and negative values require non-strict border comparisons. For [-1000000] and [1000000], the median is 0; sentinel values must not replace a real middle value.

Common Mistakes and Interview Tips

Binary searching the longer array, which can push the derived split past the end of the shorter one.
Using 0 as a missing-border stand-in instead of infinities, which corrupts comparisons on negative inputs.
Averaging with integer division or forgetting the odd-length branch, returning a truncated or doubled median.
Using element indices instead of cut counts: the search range is inclusive 0 through m, and the last value on the left is at i - 1.
Using total // 2 for the left size with the shown odd-case return; this code needs (total + 1) // 2 so the extra value is on the left.
Using strict cross comparisons rejects valid cuts with equal values. Assuming the defensive exception detects unsorted inputs is also wrong; sortedness is a precondition.
Interview tip: explain the left-size invariant and why each failed comparison fixes the search direction. Mention that merging is only the baseline, and that widened arithmetic would be needed if Java values could span the full int range.

Key Takeaway

For order statistics over sorted inputs, binary search the partition point rather than the value: a valid split exposes the answer in its borders.