One of the most famous hard problems on LeetCode is Median of Two Sorted Arrays. At first glance, it looks straightforward—you just need the median of two sorted arrays. But the catch is that the required time complexity is O(log(m + n)), which rules out the obvious approach.

Let’s walk through both the simple solution and the optimal binary search approach.

Problem Statement

Given two sorted integer arrays nums1 and nums2 of sizes m and n, return the median of all elements.

The required time complexity is:

O(log(m + n))

Example 1

Input:
nums1 = [1,2]
nums2 = [3]

Output:
2.0

Merged array:

[1,2,3]

Median = 2

Example 2

Input:
nums1 = [1,3]
nums2 = [2,4]

Output:
2.5

Merged array:

[1,2,3,4]

Median = (2 + 3) / 2 = 2.5

Solution 1: Merge and Sort (Brute Force)

The simplest idea is to combine both arrays, sort them, and then calculate the median.

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged = nums1 + nums2
        merged.sort()

        length = len(merged)

        if length % 2 == 0:
            return (merged[length // 2 - 1] + merged[length // 2]) / 2
        else:
            return merged[length // 2]

How it works

  1. Merge both arrays.
  2. Sort the merged array.
  3. If the total length is odd, return the middle element.
  4. If even, return the average of the two middle elements.

Time Complexity

  • Merging: O(m + n)
  • Sorting: O((m+n) log(m+n))

Overall:

O((m+n) log(m+n))

Space Complexity

O(m+n)

Although this solution is easy to understand, it doesn’t satisfy the problem’s required complexity.

Solution 2: Binary Search (Optimal)

To achieve O(log(min(m, n))), we use binary search on the smaller array.

Instead of merging arrays, we partition both arrays so that:

  • Every element on the left partition is less than or equal to every element on the right partition.
  • The left partition contains exactly half of the total elements.

This allows us to directly compute the median.

Step 1: Always Binary Search the Smaller Array

if len(nums1) > len(nums2):
    nums1, nums2 = nums2, nums1

Searching the smaller array guarantees logarithmic complexity.

Step 2: Calculate the Partition

Suppose

m = len(nums1)
n = len(nums2)

Total elements:

total = m + n
half = (total + 1) // 2

During binary search:

i = (l + r) // 2
j = half - i

Here,

  • i = partition index in nums1
  • j = partition index in nums2

Step 3: Get Partition Values

For every partition, we define four values.

In code:

nums1left = float("-inf") if i == 0 else nums1[i-1]
nums1right = float("inf") if i == m else nums1[i]

nums2left = float("-inf") if j == 0 else nums2[j-1]
nums2right = float("inf") if j == n else nums2[j]

Using -inf and inf handles edge cases where the partition is at the beginning or end of an array.

Step 4: Check if the Partition is Correct

The correct partition satisfies:

nums1left <= nums2right
and
nums2left <= nums1right

This means:

  • Every value on the left is less than or equal to every value on the right.

Step 5: Calculate the Median

Odd Total Length

Return the maximum value from the left partition.

max(nums1left, nums2left)

Even Total Length

Return the average of:

  • Largest value on the left
  • Smallest value on the right
(max(nums1left, nums2left) + min(nums1right, nums2right)) / 2

Step 6: Adjust Binary Search

If

nums1left > nums2right

then we moved too far right in nums1.

Move left.

r = i - 1

Otherwise,

l = i + 1

Move right.

Complete Optimal Solution

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

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

        l, r = 0, m

        while l <= r:

            i = (l + r) // 2
            j = half - i

            nums1left = float("-inf") if i == 0 else nums1[i-1]
            nums1right = float("inf") if i == m else nums1[i]

            nums2left = float("-inf") if j == 0 else nums2[j-1]
            nums2right = float("inf") if j == n else nums2[j]

            if nums1left <= nums2right and nums2left <= nums1right:

                if total % 2:
                    return max(nums1left, nums2left)

                return (
                    max(nums1left, nums2left)
                    + min(nums1right, nums2right)
                ) / 2

            if nums1left > nums2right:
                r = i - 1
            else:
                l = i + 1

Dry Run

Consider:

nums1 = [1,3]
nums2 = [2,4]

Total elements = 4

Half = 2

First partition:

nums1

1 | 3

nums2

2 | 4

Left values:

1
2

Right values:

3
4

Conditions:

1 <= 4 ✓
2 <= 3 ✓

Valid partition.

Median:

(max(1,2) + min(3,4)) / 2

= (2 + 3) / 2

= 2.5

Complexity Analysis

Brute Force

Metric

Complexity

Time

O((m+n) log(m+n))

Space

O(m+n)

Metric

Complexity

Time

O(log(min(m,n)))

Space

O(1)

Key Takeaways

  • The merge-and-sort solution is intuitive but does not meet the required time complexity.
  • The optimal solution avoids merging entirely by using binary search on the smaller array.
  • The core idea is to find a partition where every element on the left is less than or equal to every element on the right.
  • Once the correct partition is found, the median can be computed in constant time.

This problem is considered one of the best exercises for mastering binary search on partitions. While the logic may seem intimidating at first, understanding the partition conditions makes the solution much easier to reason about.