Median of Two Sorted Arrays

The problem. Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of all their values together. The overall run time should be O(log(m + n)).

Example

nums1 = [1, 3], nums2 = [2]           ->  2.0
nums1 = [1, 2], nums2 = [3, 4]        ->  2.5
nums1 = [1, 3, 8, 9], nums2 = [2, 4, 5, 7, 10]  ->  5.0

The pattern: hard binary search

The last two problems are the hardest binary searches interviews ask for. Neither searches for a value in an array. This one searches for a cut position that splits two arrays correctly; the next searches a range of distances, counting with two pointers at each step. Both still come down to the same question: which half of the search space can safely be thrown away?

The idea: binary search the cut

The median splits all m + n values into a left half and a right half where every left value is at most every right value. Suppose the left half takes i values from nums1 and j from nums2, with i + j = half (half the total, rounded up). Because both arrays are sorted, the cut is correct exactly when nums1[i−1] <= nums2[j] and nums2[j−1] <= nums1[i] — the largest on each left side doesn't pass the smallest on the other right side. If nums1[i−1] is too big, i is too large; otherwise i is too small. That's a binary search on i alone. Search the shorter array so j always stays in range.

1. Merge, then take the middle

1function findMedianSortedArrays(nums1, nums2) {2  const merged = [];3  let i = 0, j = 0;4  while (i < nums1.length || j < nums2.length) {5    if (j === nums2.length || (i < nums1.length && nums1[i] <= nums2[j])) merged.push(nums1[i++]);6    else merged.push(nums2[j++]);7  }8  const mid = Math.floor(merged.length / 2);9  return merged.length % 2 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;10}

Time O(m + n), space O(m + n).

2. Walk to the middle without storing

Only the one or two middle values matter, so run the merge's two pointers just far enough and remember the last two values passed.

1function findMedianSortedArrays(nums1, nums2) {2  const total = nums1.length + nums2.length;3  let i = 0, j = 0, prev = 0, cur = 0;4  for (let step = 0; step <= Math.floor(total / 2); step++) {   // walk to the middle5    prev = cur;6    if (j === nums2.length || (i < nums1.length && nums1[i] <= nums2[j])) cur = nums1[i++];7    else cur = nums2[j++];8  }9  return total % 2 ? cur : (prev + cur) / 2;10}

Time O(m + n), space O(1). A good first answer — then the interviewer asks for O(log).

3. Binary search the cut in the shorter array

1function findMedianSortedArrays(nums1, nums2) {2  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);   // search the shorter one3  const m = nums1.length, n = nums2.length;4  const half = Math.floor((m + n + 1) / 2);      // how many values go in the left half5  let low = 0, high = m;6  while (low <= high) {7    const i = Math.floor((low + high) / 2);      // take i values from nums1 ...8    const j = half - i;                          // ... and the rest from nums29    const left1 = i > 0 ? nums1[i - 1] : -Infinity;10    const right1 = i < m ? nums1[i] : Infinity;11    const left2 = j > 0 ? nums2[j - 1] : -Infinity;12    const right2 = j < n ? nums2[j] : Infinity;13    if (left1 <= right2 && left2 <= right1) {    // every left value <= every right value14      if ((m + n) % 2 === 1) return Math.max(left1, left2);15      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;16    }17    if (left1 > right2) high = i - 1;            // took too many from nums118    else low = i + 1;                            // took too few from nums119  }20}

Time O(log min(m, n)), space O(1). The missing neighbours at the edges count as −∞ and +∞, so a cut at either end of an array still works. The left half gets the extra value when the total is odd, which is why the odd-case median is the largest left value.

Comparing the approaches

Edge cases to test

Variations