Median of Two Sorted Arrays

HardArray Binary Search

Two weather stations each keep a sorted list of their daily temperature anomalies, meaning how far each day was above or below normal, so values can be negative. nums1 holds m values and nums2 holds n values, both in non-decreasing order. A climate report needs the median of all m + n values taken together.

The median is the middle value of the combined sorted list. When m + n is even it is the average of the two middle values, so the answer can be fractional; answers within 10^-5 of the expected value are accepted.

Merging the two lists takes O(m + n) time. Aim for O(log(min(m, n))).

Example 1

Input: nums1 = [-3,4,10], nums2 = [1,6]
Output: 4.0

Explanation: Combined, the values are [-3,1,4,6,10], and the middle one is 4.

Example 2

Input: nums1 = [2,9], nums2 = [5,7,8,12]
Output: 7.5

Explanation: Combined: [2,5,7,8,9,12], so the median is (7 + 8) / 2 = 7.5.

Example 3

Input: nums1 = [], nums2 = [-6,-1]
Output: -3.5

Explanation: One station has no data, and the median of [-6,-1] is (-6 + -1) / 2 = -3.5.

Constraints

nums1 and nums2 each hold between 0 and 1000 values, and at least one of them is non-empty.
Every value is an integer from -10^6 to 10^6.

💡 Hint 1

The median splits the combined values into a left part and a right part of (almost) equal size, where everything on the left is <= everything on the right.

💡 Hint 2

If you take i elements from nums1 for the left part, the size forces you to take half - i from nums2. So only i needs to be chosen.

💡 Hint 3

Binary search i over the shorter array: check the four values around the cut. If nums1[i-1] > nums2[j], take fewer from nums1; if nums2[j-1] > nums1[i], take more.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Instead of merging, binary search for the cut that splits the combined values into a left half of size half = floor((m + n + 1) / 2) and a right half. Work on the shorter array (swap if needed). Choosing i elements from nums1 for the left side forces j = half - i from nums2. The cut is correct when nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i], treating out-of-range neighbors as -∞ / +∞. If nums1[i-1] is too big, move i left; otherwise move it right. Once the cut is valid, the median is the largest left value when m + n is odd, and the average of the largest left value and the smallest right value when it is even. The search range is [0, min(m, n)], hence the logarithmic time.

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

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length;
  const n = nums2.length;
  const half = (m + n + 1) >> 1;
  let lo = 0;
  let hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const left1 = i > 0 ? nums1[i - 1] : -Infinity;
    const right1 = i < m ? nums1[i] : Infinity;
    const left2 = j > 0 ? nums2[j - 1] : -Infinity;
    const right2 = j < n ? nums2[j] : Infinity;
    if (left1 <= right2 && left2 <= right1) {
      const leftMax = Math.max(left1, left2);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(right1, right2)) / 2;
    }
    if (left1 > right2) hi = i - 1;
    else lo = i + 1;
  }
  return 0;
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length, half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int left1 = i > 0 ? nums1[i - 1] : Integer.MIN_VALUE;
            int right1 = i < m ? nums1[i] : Integer.MAX_VALUE;
            int left2 = j > 0 ? nums2[j - 1] : Integer.MIN_VALUE;
            int right2 = j < n ? nums2[j] : Integer.MAX_VALUE;
            if (left1 <= right2 && left2 <= right1) {
                int leftMax = Math.max(left1, left2);
                if ((m + n) % 2 == 1) return leftMax;
                return (leftMax + (double) Math.min(right1, right2)) / 2.0;
            }
            if (left1 > right2) hi = i - 1;
            else lo = i + 1;
        }
        return 0.0;
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function findMedianSortedArrays(nums1, nums2) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit