Median of Two Sorted Arrays

PracticeNeetCode ↗LeetCode ↗

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined data — in O(log(min(m, n))) time.

Example

Key Pointers

• Merging both arrays and reading off the middle works but costs O(m+n); the log time bound means binary searching a partition point instead of the data itself.
• Binary search runs on the smaller array only — that's what produces the O(log(min(m, n))) bound.
• A partition is correct once every value on its left side is no greater than every value on its right side, across both arrays combined.

Step-by-Step Analysis

1. Make sure nums1 is the smaller array, swapping if needed, since the binary search runs over it.
2. Binary search a partition index in nums1; the matching partition index in nums2 follows from how many elements the combined left half needs.
3. Read the four boundary values around both partitions, using infinities for any out-of-range edge.
4. If the left values on each side don't exceed the right values on the other side, the partition is correct — the median comes from those four boundary values, combined differently depending on whether the total length is even or odd.
5. Otherwise shift the search left or right in nums1, depending on which boundary comparison failed.

Complexity

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

Code

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    left, right = 0, m
    half = (m + n + 1) // 2

    while left <= right:
        i = left + (right - left) // 2
        j = half - i

        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")

        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 0:
                return (max(left1, left2) + min(right1, right2)) / 2
            return float(max(left1, left2))
        elif left1 > right2:
            right = i - 1
        else:
            left = i + 1

    return 0.0

Code Explanation

How the solution above works, piece by piece.

1. Swap so nums1 is the shorter array; the binary search runs over its possible cut positions 0..m, which is O(log(min(m, n))).
2. half = (m + n + 1) // 2 is how many elements belong on the left. Choosing cut i in nums1 forces j = half - i in nums2.
3. left1, right1, left2, right2 are the values on each side of the two cuts, with ±∞ standing in when a cut is at an edge.
4. The cut is correct when left1 <= right2 and left2 <= right1. Then the median is max(left) for an odd total, or the average of max(left) and min(right) for an even total.
5. If left1 > right2, too much of nums1 is on the left: move the cut left. Otherwise move it right.

Visual Walkthrough

Running it on nums1 = [1, 3], nums2 = [2]:

Video Explanation

NeetCode — Binary Search, LeetCode 4