Median of Two Sorted Arrays

Difficulty: Hard

Problem

You are given two arrays nums1 and nums2, each already sorted, with m and n elements respectively. Compute the median of all m + n values taken together. Your algorithm should run in O(log(m+n)) time.

Example

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: Combining the values gives [1, 2, 3]; the middle element is 2, so the median is 2.0.

Brute-force approach

Merge both sorted arrays into one sorted array, then directly find the median from the merged array.

Steps

  1. Merge nums1 and nums2 into a single sorted array
  2. If total length is odd: return the middle element
  3. If total length is even: return the average of the two middle elements

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

Trade-offs

  • Merging takes O(m+n) time: doesn't meet the O(log(m+n)) requirement
  • Uses O(m+n) extra space for the merged array
  • Processes every element when we only need elements near the median

Optimal approach

Key insight: Instead of merging, we find a partition that splits both arrays so that exactly half the total elements are on the left. Binary search on the shorter array finds this partition in O(log(min(m, n))).

Binary search on the shorter array to find the correct partition point that divides both arrays into left and right halves such that all left elements are <= all right elements.

Steps

  1. Ensure nums1 is the shorter array
  2. Binary search: left=0, right=m
  3. For each i, compute j = (m+n+1)/2 - i
  4. Check partition validity using boundary elements
  5. If valid: compute median from boundary elements
  6. If leftMax1 > rightMin2: right = i-1
  7. If leftMax2 > rightMin1: left = i+1

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

Pseudocode

function findMedian(nums1, nums2):
    // Ensure nums1 is the shorter array
    if len(nums1) > len(nums2): swap(nums1, nums2)
    m = len(nums1), n = len(nums2)
    left = 0, right = m
    
    while left <= right:
        i = (left + right) / 2   // partition in nums1
        j = (m + n + 1) / 2 - i // partition in nums2
        
        leftMax1 = nums1[i-1] if i > 0 else -INF
        rightMin1 = nums1[i] if i < m else +INF
        leftMax2 = nums2[j-1] if j > 0 else -INF
        rightMin2 = nums2[j] if j < n else +INF
        
        if leftMax1 <= rightMin2 and leftMax2 <= rightMin1:
            if (m + n) is odd: return max(leftMax1, leftMax2)
            else: return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2
        else if leftMax1 > rightMin2:
            right = i - 1
        else:
            left = i + 1

Hints

  • Binary search on the shorter array to find the correct partition point
  • The partition divides both arrays so that all elements on the left are <= all elements on the right
  • The median comes from the elements around the partition boundary

Complexity questions

What is the time complexity of merging then finding the median?

O(m + n). Merging two sorted arrays takes O(m+n). Finding the median from a merged array is O(1).

What is the time complexity of the binary search partition approach?

O(log(min(m, n))). We binary search on the shorter array of length min(m, n), giving O(log(min(m, n))).

What is the space complexity of the optimal approach?

O(1). We only use a constant number of variables, no extra arrays needed. O(1) space.

Check your understanding of Median of Two Sorted Arrays

What is the median of [1, 2, 3, 4, 5]?

3. For an odd-length array, the median is the middle element. [1, 2, 3, 4, 5] has 5 elements, so the median is the 3rd element: 3.

What is the median of [1, 2, 3, 4]?

2.5. For an even-length array, the median is the average of the two middle elements. Middle elements are 2 and 3, so median = (2+3)/2 = 2.5.

Why can't we just merge and find the middle in O(log(m+n))?

Merging takes O(m+n) time which is too slow. We need a binary search approach. Merging two arrays takes O(m+n) time. The problem requires O(log(m+n)), which means we need binary search, not full merge.

Related problems

Keep practising