Median of Two Sorted Arrays

The median only depends on the value(s) at the middle position(s) of the fully merged, sorted sequence — not on having the whole merged array materialized. So walk nums1 and nums2 with a standard merge-sort merge step (two pointers, always advance the smaller front), but instead of storing every merged value, just keep the current and previous value as you count up to the halfway point. This gets O(m+n) time and true O(1) extra space, which already beats the naive “concatenate, sort, index into the middle” approach (O((m+n) log(m+n))). It still is not the O(log(m+n)) the problem asks for, because it always walks roughly half of both arrays no matter what.

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        total = m + n
        half = total // 2
        i = j = 0
        prev = curr = 0
        for _ in range(half + 1):
            prev = curr
            if i < m and (j >= n or nums1[i] <= nums2[j]):
                curr = nums1[i]
                i += 1
            else:
                curr = nums2[j]
                j += 1
        if total % 2 == 1:
            return float(curr)
        return (prev + curr) / 2

Reframe the problem: instead of merging, look for a way to partition both arrays with a single cut each, so that everything to the left of both cuts (call it the “left group”) is exactly half = (m + n + 1) // 2 elements, and every element in the left group is <= every element in the right group. If such a partition exists, the median is computable directly from the four values that straddle the two cuts — no merging required.

Binary search for that partition on the shorter array (always swap so nums1 is the shorter one — this bounds the search space and guarantees j = half - i stays in valid range). For a candidate cut i in nums1, the matching cut in nums2 is forced: j = half - i. Define the four boundary values (using -inf/+inf when a cut lands at an array edge):

• left1 = nums1[i-1] if i > 0 else -inf
• right1 = nums1[i] if i < m else +inf
• left2 = nums2[j-1] if j > 0 else -inf
• right2 = nums2[j] if j < n else +inf

The partition is valid exactly when left1 <= right2 and left2 <= right1. If left1 > right2, i is too far right, so binary search left (hi = i - 1); if left2 > right1, i is too far left, so binary search right (lo = i + 1).

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)
        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
            elif left1 > right2:
                hi = i - 1
            else:
                lo = i + 1

Tracing the file example nums1 = [1,3], nums2 = [2] — note the code swaps the arrays first, because [1,3] is longer than [2] (so the A row below holds the post-swap nums1 = [2]). Watch the two boundary checks L1 <= R2 and L2 <= R1 steer the search: the first split fails L2 <= R1, the cut in A moves right, and the corrected split reads the median straight off the left boundary chips:

That trace fires only the L2 > R1 failure — the mirror case, L1 > R2, would instead move the cut left via hi = i - 1. Contrast the even-length example from the statement, nums1 = [1,2], nums2 = [3,4] (half = 2): the first guess i = 1 has left2 = 3 > right1 = 2, so it also steers right to i = 2 (boundaries L1 = 2, R1 = +inf, L2 = -inf, R2 = 3), which passes both checks. Since m + n = 4 is even, the median is the average of the two middle values: (max(L1, L2) + min(R1, R2)) / 2 = (2 + 3) / 2 = 2.5 — matching the expected output. An odd m + n, like the visualizer’s example, uses only max(L1, L2).

Why it’s correct: any partition where the left group has exactly half elements and every left element is <= every right element is a valid split point of the fully merged array — the four boundary values are precisely the elements adjacent to that split, so the median can be read off them directly, without materializing the merge. Binary search finds such a partition because moving i right can only increase left1/right1 and (via j = half - i shrinking) decrease left2/right2 — so “is i too far right” (left1 > right2) is a monotonic condition. Complexity: binary search runs over the shorter array’s index range [0, m] where m = min(len(nums1), len(nums2)), and each check is O(1), giving O(log(min(m, n))) time, O(1) space — satisfying the O(log(m+n)) requirement since log(min(m,n)) <= log(m+n).