Median of Two Sorted Arrays 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #4: Median of Two Sorted Arrays — one of the hardest problems on LeetCode! This is the boss battle. 🏆

💡 Think of it like this: You have two sorted lists of numbers. If you merged them into one big sorted list, what would the middle number be? The challenge: do it in O(log(m+n)) time, not O(m+n).

# Example:
nums1 = [1, 3]
nums2 = [2]
# Merged: [1, 2, 3] → median = 2

nums1 = [1, 2]
nums2 = [3, 4]
# Merged: [1, 2, 3, 4] → median = (2+3)/2 = 2.5

The Key Insight — Binary Search on Partition:

Instead of merging, we find a cut point in each array that divides all numbers into a left half and right half, where left half ≤ right half and both halves have equal size.

Binary search on the SHORTER array for efficiency
For each cut in array A, calculate the corresponding cut in array B
A valid partition: max(left_A, left_B) ≤ min(right_A, right_B)
Median = average of max(left) and min(right) for even total, or max(left) for odd

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Complexity: Time O(log(min(m,n))) — binary search on the shorter array. Space O(1). This is the required optimal solution.

📋 Instructions

Find median of nums1=[1,3] and nums2=[2]. Then nums1=[1,2] and nums2=[3,4].

Binary search on the shorter array. For each partition in A, calculate the corresponding partition in B. Valid when max(leftA, leftB) <= min(rightA, rightB).

⚠️ Try solving it yourself first — you'll learn more!

def findMedian(nums1, nums2):
    # Always binary search on the shorter array
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A
    
    total = len(A) + len(B)
    half = total // 2
    lo, hi = 0, len(A) - 1
    
    while True:
        i = (lo + hi) // 2          # Cut in A
        j = half - i - 2            # Cut in B
        
        a_left  = A[i] if i >= 0 else float('-inf')
        a_right = A[i+1] if i+1 < len(A) else float('inf')
        b_left  = B[j] if j >= 0 else float('-inf')
        b_right = B[j+1] if j+1 < len(B) else float('inf')
        
        if a_left <= b_right and b_left <= a_right:  # Valid!
            if total % 2:  # Odd
                return min(a_right, b_right)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        elif a_left > b_right:
            hi = i - 1  # Move left in A
        else:
            lo = i + 1  # Move right in A

🧪 Test Cases

Input

findMedianSortedArrays([1,3], [2])

Expected

2

Test case 1

Input

findMedianSortedArrays([1,2], [3,4])

Expected

2.5

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›