Median of Two Sorted Arrays – Solution & Complexity

Q: What is the time and space complexity of Median of Two Sorted Arrays?

The optimal Median of Two Sorted Arrays solution runs in `O(log(min(m, n)))` time and `O(1)` space. Binary search for the correct partition on the smaller array.

Q: What is the most efficient way to solve Median of Two Sorted Arrays?

Binary search for the correct partition on the smaller array. This gives `O(log(min(m, n)))` time complexity, and is a classic arrays, binary search, and divide and conquer problem.

Q: How do you solve Median of Two Sorted Arrays in Python & JavaScript?

We provide a worked Median of Two Sorted Arrays solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Median of Two Sorted Arrays an easy or hard interview question?

Median of Two Sorted Arrays is generally rated **Hard**. It tests arrays, binary search, and divide and conquer, which are common coding-interview patterns.

1. Think in Terms of a Partition

The median splits the combined sorted values into a left half and a right half.
Every value on the left must be less than or equal to every value on the right.
If we can find that split without merging, we get logarithmic time.

2. Binary Search the Smaller Array

Choose how many values come from nums1 on the left side, and infer how many must come from nums2.
Searching the smaller array keeps the binary search range as small as possible and avoids invalid indexes.
The left side should contain (m + n + 1) // 2 values so odd lengths put the median on the left.

if len(nums1) > len(nums2):
    return find_median_sorted_arrays(nums2, nums1)

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

3. Check the Partition Boundaries

For a partition i in nums1, use j = half - i in nums2.
Compare only four boundary values: left and right around each partition.
Sentinels -inf and inf make empty sides easy to handle.

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')

4. Move Toward a Valid Split

A partition is valid when left1 <= right2 and left2 <= right1.
If left1 > right2, too many values were taken from nums1, so move left.
Otherwise, too few values were taken from nums1, so move right.

if left1 <= right2 and left2 <= right1:
    # Compute the median from the boundary values.
elif left1 > right2:
    hi = i - 1
else:
    lo = i + 1

5. Final Complete Solution

For odd total length, the median is the largest value on the left side.
For even total length, average the largest left value and smallest right value.
Time complexity is O(log(min(m, n))), and extra space complexity is O(1).

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

    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    lo, hi = 0, m

    while lo <= hi:
        i = (lo + hi) // 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 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2.0
        if left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

    return 0.0

Median of Two Sorted Arrays – Solution & Complexity

1. Think in Terms of a Partition

2. Binary Search the Smaller Array

3. Check the Partition Boundaries

4. Move Toward a Valid Split

5. Final Complete Solution

FAQ

What is the time and space complexity of Median of Two Sorted Arrays?

What is the most efficient way to solve Median of Two Sorted Arrays?

How do you solve Median of Two Sorted Arrays in Python & JavaScript?

Is Median of Two Sorted Arrays an easy or hard interview question?