Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Two arrays are already sorted. If they were merged into one larger sorted array, the task would be to return the middle value.

For an odd total length, that middle value is a single number.

For an even total length, the median is the average of the two middle numbers.

The catch is that the problem asks for better than a full merge. So the real question is:

how can the middle be found without actually building the whole combined sorted array?

The key insight

The median only depends on the boundary around the middle. It does not depend on the exact order of every element far away from that boundary.

That leads to a much better idea than merging:

  • split the two arrays into a left half and a right half
  • make sure the left half contains exactly half of the total elements, or one extra when the total length is odd
  • make sure every value in the left half is less than or equal to every value in the right half

Once that partition is correct, the median is immediate:

  • odd total length: the answer is the largest value on the left side
  • even total length: the answer is the average of the largest left value and the smallest right value

How to derive the optimal solution

The naive approach is to merge both arrays and read the middle. That is simple, but it costs O(m + n) time.

To do better, the solution has to avoid touching most elements.

Because both arrays are sorted, a partition choice in one array determines the matching partition in the other array. If i elements are taken from the first array into the left half, then the left half must take exactly left_size - i elements from the second array.

Now the problem becomes finding the correct i.

For any partition, only four boundary values matter:

  • the last value on the left side of the first array
  • the first value on the right side of the first array
  • the last value on the left side of the second array
  • the first value on the right side of the second array

If the left boundary from the first array is too large, the partition in that array is too far right, so it must move left.

If the left boundary from the second array is too large, the partition in the first array is too far left, so it must move right.

That decision is monotonic, which means binary search works. Searching the smaller array gives the optimal time complexity:

  • Time: O(log(min(m, n)))
  • Extra space: O(1)

Best approaches

The partition-based binary search is the best default because it is both optimal and iterative.

There is also a closely related k-th element approach that repeatedly discards half of one remaining search range. That approach is also efficient and often easier to connect to the general “find the k-th smallest element in two sorted arrays” problem.

For this exact LeetCode problem, the partition method is usually the cleanest way to think about the median directly.

Python solution

from typing import List, Tuple


class Solution:
    def findMedianSortedArrays(
        self,
        first_numbers: List[int],
        second_numbers: List[int],
    ) -> float:
        smaller_numbers, larger_numbers = self._order_by_length(
            first_numbers,
            second_numbers,
        )
        total_length = len(smaller_numbers) + len(larger_numbers)
        left_partition_size = (total_length + 1) // 2

        low = 0
        high = len(smaller_numbers)

        while low <= high:
            smaller_left_count = (low + high) // 2
            larger_left_count = left_partition_size - smaller_left_count

            smaller_left, smaller_right = self._partition_bounds(
                smaller_numbers,
                smaller_left_count,
            )
            larger_left, larger_right = self._partition_bounds(
                larger_numbers,
                larger_left_count,
            )

            # A valid partition means everything on the left is <= everything
            # on the right across both arrays.
            if smaller_left <= larger_right and larger_left <= smaller_right:
                return self._compute_median(
                    total_length=total_length,
                    left_max=max(smaller_left, larger_left),
                    right_min=min(smaller_right, larger_right),
                )

            if smaller_left > larger_right:
                high = smaller_left_count - 1
            else:
                low = smaller_left_count + 1

        raise ValueError("Input arrays must be sorted in non-decreasing order.")

    @staticmethod
    def _order_by_length(
        first_numbers: List[int],
        second_numbers: List[int],
    ) -> Tuple[List[int], List[int]]:
        if len(first_numbers) <= len(second_numbers):
            return first_numbers, second_numbers
        return second_numbers, first_numbers

    @staticmethod
    def _partition_bounds(
        numbers: List[int],
        left_count: int,
    ) -> Tuple[float, float]:
        left_value = numbers[left_count - 1] if left_count > 0 else float("-inf")
        right_value = numbers[left_count] if left_count < len(numbers) else float("inf")
        return left_value, right_value

    @staticmethod
    def _compute_median(
        total_length: int,
        left_max: float,
        right_min: float,
    ) -> float:
        if total_length % 2 == 1:
            return float(left_max)
        return (left_max + right_min) / 2.0

Why this works

The binary search is not looking for a value. It is looking for a partition where the two left-side boundary values are both less than or equal to the opposite right-side boundary values.

Once that happens, the combined left half contains exactly the elements that must come before the median, and the combined right half contains exactly the elements that must come after it.

That is the whole trick:

the median can be recovered from the partition edges alone, so the full merge is unnecessary.

Practical takeaway

This problem becomes much easier once it is reframed from “merge two sorted arrays” to “find the correct split between left half and right half.”

If the partition idea feels abstract at first, remember the goal is only to make these two statements true:

  • the left side has the right number of elements
  • nothing on the left is greater than anything on the right

When both are true, the median is sitting right on the boundary.