4. Median of Two Sorted ArraysHard

Median of Two Sorted Arrays

HardArrayBinary SearchDivide and Conquer·AmazonGoogleApple

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

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

Output:2.00000

merged array = [1,2,3] and median is 2.

Example 2:

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

Output:2.50000

merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶

Suboptimal Approach — Merging Both Arrays

O(m + n) Time

👀

Linear Merge (Two Pointers)

Time O(m + n)Space O(m + n)

The simplest way to find the requested median is to directly merge these two already sorted arrays together using Two Pointers into a massive array. Then, locate the exact middle coordinate of this new structure.

1Initialize empty array merged_array.
2Loop while we still have elements in either nums1 or nums2, picking the smallest of the two pointers and appending it.
3Once merged_array is fully populated, find the median by taking merged[(len)/2].

Thoughts: While this solution conceptually makes sense, it strictly operates at an $O(m + n)$ runtime limit, which doesn't fulfill the $O(log(m+n))$ constraint! We must not physically merge the arrays.

Optimal Approach — Binary Search over Partitions

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

✂️

Finding the Ideal Left Half

Time O(log min(m, n))Space O(1)

By definition, a median splits an entire dataset exactly into two halves: a Left Half (all smaller values) and a Right Half (all greater values). Since our arrays are already strictly sorted, if we can dynamically partition both arrays into left and right chunks such that the combined Left is exactly half the total size and all left values are <= all right values, we've found the mathematical median without assembling the array.

We binary search over the strictly smaller array (let's call it A) to find a partition. Using this, we immediately know where the partition in B must be to maintain the "exactly half the elements on the left side" rule: j = total_half - i - 2.

1Ensure A is the smaller array to improve speed and prevent out-of-bounds indexing in B. Set half = (len(A) + len(B)) // 2.
2Binary search the partition index i on A from 0 to len(A)-1.
3Derive the corresponding index j in B via j = half - i - 2.
4Extract 4 boundary values surrounding the partition lines: Aleft, Aright, Bleft, Bright, substituting $\pm\infty$ for out-of-bounds values.
5If cross-conditions are met (Aleft <= Bright AND Bleft <= Aright), the partition is valid! Return the median formula based on total parity.
6If Aleft > Bright, the partition line in A is physically placed too far right. We must shrink right bound: r = i - 1.
7If Bleft > Aright, the partition line is too far left. Go right: l = i + 1.

READYPress ▶ or step forward to begin.

✓

—

nums1

nums2

Executing Code

class Solution:

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

        A, B = nums1, nums2

        total = len(nums1) + len(nums2)

        half = total // 2

        if len(B) < len(A):

            A, B = B, A

        l, r = 0, len(A) - 1

        while True:

            i = (l + r) // 2

            j = half - i - 2

            Aleft = A[i] if i >= 0 else float("-infinity")

            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")

            Bleft = B[j] if j >= 0 else float("-infinity")

            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

            if Aleft <= Bright and Bleft <= Aright:

                if total % 2:

                    return min(Aright, Bright)

                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2

            elif Aleft > Bright:

                r = i - 1

            else:

                l = i + 1

Discussion

…

Loading comments…

LeetMotion