{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Median of Two Sorted Arrays – Solution & Complexity

Interview solutions
/
Median of Two Sorted Arrays

Solution Walkthrough

  1. Step 1: Think in Terms of a Partition

    • The median splits the combined sorted values into a left half and a right half.
    • Every value on the left must be less than or equal to every value on the right.
    • If we can find that split without merging, we get logarithmic time.

  2. Step 2: Binary Search the Smaller Array

    • Choose how many values come from nums1 on the left side, and infer how many must come from nums2.
    • Searching the smaller array keeps the binary search range as small as possible and avoids invalid indexes.
    • The left side should contain (m + n + 1) // 2 values so odd lengths put the median on the left.
    if len(nums1) > len(nums2):
    return find_median_sorted_arrays(nums2, nums1)

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

  3. Step 3: Check the Partition Boundaries

    • For a partition i in nums1, use j = half - i in nums2.
    • Compare only four boundary values: left and right around each partition.
    • Sentinels -inf and inf make empty sides easy to handle.
    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')

  4. Step 4: Move Toward a Valid Split

    • A partition is valid when left1 <= right2 and left2 <= right1.
    • If left1 > right2, too many values were taken from nums1, so move left.
    • Otherwise, too few values were taken from nums1, so move right.
    if left1 <= right2 and left2 <= right1:
    # Compute the median from the boundary values.
elif left1 > right2:
    hi = i - 1
else:
    lo = i + 1

  5. Step 5: Final Complete Solution

    • For odd total length, the median is the largest value on the left side.
    • For even total length, average the largest left value and smallest right value.
    • Time complexity is O(log(min(m, n))), and extra space complexity is O(1).
    def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        return find_median_sorted_arrays(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.0
        if left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

    return 0.0

FAQ

See also

Practice Median of Two Sorted Arrays online (run code in the browser)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)Koko Eating Bananas solution (medium)Longest Increasing Subsequence solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?