Median of Two Sorted Arrays

You are given two integer arrays nums1 and nums2, each already sorted in non-decreasing order. Either one may be empty, but not both.

Return the median of all the numbers from both arrays taken together. If the combined count is odd, the median is the middle value of the merged order; if it is even, it is the average of the two middle values (so the answer can be a fraction such as 5.5).

Aim for a running time of O(log(m + n)), where m and n are the lengths of the arrays. Answers within 10^-5 of the true median are accepted.

Example 1

Example 2

Example 3

Constraints

• 0 <= nums1.length, nums2.length <= 1000
• 1 <= nums1.length + nums2.length <= 2000
• -106 <= nums1[i], nums2[i] <= 106
• Both arrays are sorted in non-decreasing order.

Pattern Path · Binary Search · problem 65 of 169

Start simple

Merge the two arrays like the merge step of merge sort and read the middle element(s): O(m + n) time, O(m + n) space (or O(1) if you only walk to the middle).

The key idea

The median splits the combined numbers into a left half and a right half of equal size (the left half gets the extra one when the total is odd), with every left value <= every right value. Instead of building the merge, we search for that split directly.

Suppose the left half takes the first i elements of the shorter array a. Since the left half must hold half = (m + n + 1) / 2 elements, it must take exactly j = half - i elements of b. Both arrays are sorted, so the split is valid exactly when the two cross conditions hold: a[i-1] <= b[j] and b[j-1] <= a[i].

These conditions are monotone in i. If a[i-1] > b[j], we took too much of a and must move left. If b[j-1] > a[i], we took too little and must move right. That is a binary search on i in [0, m]. Missing neighbours at the edges are treated as −∞ or +∞, so empty sides never block a split.

Once the split is found, the median is the largest left value (odd total) or the average of the largest left and smallest right values (even total). Searching the shorter array keeps j in range and gives O(log(min(m, n))) time.

Complexity

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

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Binary search over the shorter array.
        a, b = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
        m, n = len(a), len(b)
        half = (m + n + 1) // 2  # size of the left half (it gets the extra element when odd)

        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2   # elements taken from a
            j = half - i         # elements taken from b
            a_left = a[i - 1] if i > 0 else float("-inf")
            a_right = a[i] if i < m else float("inf")
            b_left = b[j - 1] if j > 0 else float("-inf")
            b_right = b[j] if j < n else float("inf")

            if a_left > b_right:
                hi = i - 1       # took too many from a
            elif b_left > a_right:
                lo = i + 1       # took too few from a
            else:
                # Every left element <= every right element: the cut is the median.
                left_max = max(a_left, b_left)
                if (m + n) % 2 == 1:
                    return float(left_max)
                return (left_max + min(a_right, b_right)) / 2

JavaScript

var findMedianSortedArrays = function(nums1, nums2) {
  // Binary search over the shorter array.
  const [a, b] = nums1.length <= nums2.length ? [nums1, nums2] : [nums2, nums1];
  const m = a.length, n = b.length;
  const half = Math.floor((m + n + 1) / 2); // size of the left half (it gets the extra element when odd)

  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2); // elements taken from a
    const j = half - i;                  // elements taken from b
    const aLeft = i > 0 ? a[i - 1] : -Infinity;
    const aRight = i < m ? a[i] : Infinity;
    const bLeft = j > 0 ? b[j - 1] : -Infinity;
    const bRight = j < n ? b[j] : Infinity;

    if (aLeft > bRight) {
      hi = i - 1; // took too many from a
    } else if (bLeft > aRight) {
      lo = i + 1; // took too few from a
    } else {
      // Every left element <= every right element: the cut is the median.
      const leftMax = Math.max(aLeft, bLeft);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(aRight, bRight)) / 2;
    }
  }
};

What the interviewer is checking

The interviewer wants to see you binary search on a partition position rather than on values, and handle the boundary cases (empty halves, odd totals) cleanly under pressure.

Mistakes to avoid

• Searching the longer array, which lets j go negative or past the end.
• Mishandling the edges: when i or j is 0 or at the end, use −∞/+∞ instead of indexing out of bounds.
• Integer division in the even case, which turns 5.5 into 5.
• Getting the half size off by one so the odd case reads the wrong side.

Follow-ups to expect

• Find the k-th smallest element of the two arrays. (Same partition idea with k on the left.)
• What if there are k sorted arrays? (Binary search on value, count with bisect.)
• What if the data is a stream? (Two heaps holding each half.)

In real software

Databases and analytics engines compute medians and percentiles across sorted shards or partitions without merging them, using the same "choose a cut in each sorted run" search.

Practice next