Q52: Median of Two Sorted Arrays. - DSA Patterns (Multi-Lang)

In Simple Words: Binary search on the partition of the smaller array. Partition both arrays such that leftPartitionSize === (M + N + 1) / 2. Valid when maxLeft1 <= minRight2 and maxLeft2 <= minRight1.

Time: $O(\log(\min(M, N)))$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    l, r = 0, m
    while l <= r:
        i = (l + r) // 2
        j = (m + n + 1) // 2 - i
        max_l1 = float('-inf') if i == 0 else nums1[i - 1]
        min_r1 = float('inf') if i == m else nums1[i]
        max_l2 = float('-inf') if j == 0 else nums2[j - 1]
        min_r2 = float('inf') if j == n else nums2[j]

        if max_l1 <= min_r2 and max_l2 <= min_r1:
            if (m + n) % 2 == 1:
                return float(max(max_l1, max_l2))
            return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
        elif max_l1 > min_r2:
            r = i - 1
        else:
            l = i + 1
    return 0.0