Median of Two Sorted Arrays

Examples

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

Merged, the combined sorted list is [1, 2, 3], and its single middle value is 2.

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

Merged, the combined list is [1, 2, 3, 4]; the two middle values are 2 and 3, and their average is 2.5.

Input: nums1 = [], nums2 = [1]
Output: 1

One list is empty, so the combined list is just [1], whose median is 1.

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

Approach

The direct approach is to merge both sorted lists into one, the same way the merge step of merge sort works, and then read off the middle value (or values) of the result. This is easy to reason about, but it looks at every element, so it can never be faster than O(m + n).

The faster approach never actually merges anything. The full merged list would have a "left half" and a "right half" split right at the median. Instead of building that list, binary search for where that split line falls inside the shorter of the two arrays — call that position i. Because the combined left half always needs the same total number of elements, the matching split point j in the other array is then just arithmetic: j = halfway point - i. A split is correct once every value just left of the line, in both arrays, is <= every value just right of the line, in both arrays; if it isn't, binary search nudges i up or down and tries again. Once the correct split is found, the median can be read directly off the (at most) four values sitting right at the boundary — no merging required.

Solutions

Brute Force — Merge, Then Read the Middle

Merge the two sorted lists into one sorted list the same way merge sort does, then look at the middle element (or average the two middle elements). Correct and easy to follow, but it always looks at every element.

function findMedianSortedArrays(nums1, nums2) {
  const merged = [];
  let i = 0;
  let j = 0;

  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) {
      merged.push(nums1[i++]);
    } else {
      merged.push(nums2[j++]);
    }
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);

  const n = merged.length;
  const mid = Math.floor(n / 2);

  if (n % 2 === 1) {
    return merged[mid];
  }
  return (merged[mid - 1] + merged[mid]) / 2;
}

Time: O(m + n) · Space: O(m + n)

Optimal — Binary Search on the Partition

Binary search over the shorter array for the split point that divides both arrays combined into a valid left half and right half, then read the median directly off the values at that boundary.

function findMedianSortedArrays(nums1, nums2) {
  // Always binary search over the shorter array.
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  const m = nums1.length;
  const n = nums2.length;
  const half = Math.floor((m + n + 1) / 2);

  let low = 0;
  let high = m;

  while (low <= high) {
    const i = Math.floor((low + high) / 2); // elements of nums1 in the left half
    const j = half - i; // elements of nums2 in the left half

    const left1 = i === 0 ? -Infinity : nums1[i - 1];
    const right1 = i === m ? Infinity : nums1[i];
    const left2 = j === 0 ? -Infinity : nums2[j - 1];
    const right2 = j === n ? Infinity : nums2[j];

    if (left1 <= right2 && left2 <= right1) {
      if ((m + n) % 2 === 1) {
        return Math.max(left1, left2);
      }
      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
    } else if (left1 > right2) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }

  return -1; // unreachable for valid, sorted inputs
}

Time: O(log(min(m, n))) · Space: O(1)