Median Of Two Sorted Arrays

Tags

Median Of Two Sorted Arrays

Category

Searching

Difficulty

Very Hard

Problem Statement

Given two sorted arrays of possibly different sizes, find the median of the combined sorted array. The overall run time complexity should be O(log(min(m, n))) where m and n are the lengths of the two arrays.

Intuition

The median partitions a sorted sequence into two equal halves. Instead of merging the two arrays (which would be O(m+n)), we can binary search for the correct partition point. We binary search on the smaller array to find how many elements from it go into the left half. The remaining left-half elements come from the larger array. At the correct partition, the maximum of the left halves must be less than or equal to the minimum of the right halves.

Approach

  1. Ensure array1 is the smaller array (swap if necessary).
  2. Let m = len(array1), n = len(array2), and halfTotal = (m + n + 1) / 2.
  3. Binary search on array1 with low = 0, high = m: a. partition1 = (low + high) / 2 — number of elements from array1 in the left half. b. partition2 = halfTotal - partition1 — number of elements from array2 in the left half. c. Compute boundary values:
    • maxLeft1 = array1[partition1 - 1] (or -infinity if partition1 == 0)
    • minRight1 = array1[partition1] (or +infinity if partition1 == m)
    • maxLeft2 = array2[partition2 - 1] (or -infinity if partition2 == 0)
    • minRight2 = array2[partition2] (or +infinity if partition2 == n) d. If maxLeft1 <= minRight2 and maxLeft2 <= minRight1: correct partition found.
    • If total length is odd: median = max(maxLeft1, maxLeft2).
    • If total length is even: median = (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2. e. If maxLeft1 > minRight2: move high = partition1 - 1. f. If maxLeft2 > minRight1: move low = partition1 + 1.

Pseudocode

function medianOfTwoSortedArrays(nums1, nums2):
    if length(nums1) > length(nums2):
        swap(nums1, nums2)

    m = length(nums1)
    n = length(nums2)
    low = 0
    high = m
    halfTotal = (m + n + 1) / 2

    while low <= high:
        partition1 = (low + high) / 2
        partition2 = halfTotal - partition1

        maxLeft1 = -infinity if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = +infinity if partition1 == m else nums1[partition1]
        maxLeft2 = -infinity if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = +infinity if partition2 == n else nums2[partition2]

        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            if (m + n) is odd:
                return max(maxLeft1, maxLeft2)
            else:
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
        elif maxLeft1 > minRight2:
            high = partition1 - 1
        else:
            low = partition1 + 1

Time & Space Complexity

  • Time: O(log(min(m, n))) — Binary search on the smaller array.
  • Space: O(1) — Only a constant number of variables.

Key Insights

  • Always binary search on the smaller array to guarantee O(log(min(m, n))) time.
  • The sentinel values (-infinity and +infinity) elegantly handle edge cases where one partition is empty.
  • The partition condition maxLeft1 <= minRight2 and maxLeft2 <= minRight1 ensures the left halves contain all elements that would appear before the median in a merged array.
  • This is one of the most elegant applications of binary search on a non-obvious search space.

Edge Cases

  • One array is empty: the median is simply the median of the other array.
  • Arrays of length 1: careful handling of partition boundaries.
  • All elements in one array are smaller than all elements in the other.
  • Both arrays have the same elements: the median is that repeated value.
  • Even total length vs. odd total length: different formulas for the final answer.

Linked mentions