LeetCode 4: Median of Two Sorted Arrays

Problem Statement

LeetCode 4, Median of Two Sorted Arrays, is a hard-level challenge where you find the median of two sorted arrays, nums1 (length m) and nums2 (length n), as if they were combined into one sorted array. The median is the middle number if the total length is odd, or the average of the two middle numbers if even. The key requirement is doing this in O(log(min(m, n))) time, pushing us toward a clever solution like binary search instead of a full merge.

Constraints

  • nums1.length == m, nums2.length == n.
  • 0 <= m, n <= 1000: Arrays can be empty or up to 1000 elements.
  • 1 <= m + n <= 2000: Total elements range from 1 to 2000.
  • -10^6 <= nums1[i], nums2[i] <= 10^6: Integers span a wide range.
  • Both arrays are sorted in ascending order.

Example

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: Merged = [1, 2, 3], length 3 (odd), median is 2.

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: Merged = [1, 2, 3, 4], length 4 (even), median is (2 + 3) / 2 = 2.5.

Input: nums1 = [], nums2 = [1]
Output: 1.0
Explanation: Merged = [1], length 1 (odd), median is 1.

Understanding the Problem

The median is the middle value of the merged sorted array, but we don’t want to merge it fully because that’s slow. For m + n elements:

  • Odd: Median is the ((m + n + 1) / 2)-th number (1-based).
  • Even: Average of the ((m + n) / 2)-th and ((m + n) / 2 + 1)-th numbers.

The O(log(min(m, n))) time suggests a search approach. We’ll explore three solutions:

  • Brute Force: Merge and sort.
  • Merge Up to Median: Merge only to the median point.
  • Binary Search: Partition-based optimal solution.

Solution 1: Brute Force (Merge and Sort)

Explanation

This simple method combines both arrays into one big list and finds the median. It’s easy but not fast enough for the problem’s goal.

  1. Concatenate Arrays.
  • Put all numbers from nums1 and nums2 into one list.

2. Sort the Result.

  • Sort the list so we can find the middle spot(s).

3. Compute Median.

  • If the length is odd, take the middle number; if even, average the two middle numbers.

Step-by-Step Example

Example 1: nums1 = [1, 3], nums2 = [2], total length = 3

We have nums1 = [1, 3] and nums2 = [2], totaling 3 numbers. Since 3 is odd, the median is the 2nd number.

  • Goal: Find the 2nd number in the merged list.
  • Result for reference: Merged is [1, 2, 3], 2nd number is 2, so median is 2.0.
  • Start: Combine nums1 and nums2 into [1, 3, 2].
    • This gathers all numbers together.
  • Sort: Change [1, 3, 2] to [1, 2, 3].
    • Puts them in order to find the middle.
  • Result: Length is 3, so take the 2nd number (middle, index 1), which is 2.
    • That’s the median for an odd total.

Example 2: nums1 = [1, 2], nums2 = [3, 4], total length = 4

Now, nums1 = [1, 2] and nums2 = [3, 4] total 4 numbers. Since 4 is even, the median is the average of the 2nd and 3rd numbers.

  • Goal: Find the 2nd and 3rd numbers and average them.
  • Result for reference: Merged is [1, 2, 3, 4], 2nd is 2, 3rd is 3, median is (2 + 3) / 2 = 2.5.
  • Start: Combine into [1, 2, 3, 4].
    • All numbers in one list.
  • Sort: Already sorted as [1, 2, 3, 4].
    • Confirms the order.
  • Result: Length is 4, take 2nd (index 1) and 3rd (index 2): 2 and 3. Average: (2 + 3) / 2 = 2.5.
    • This is the median for an even total.

Code

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    merged = sorted(nums1 + nums2)
    n = len(merged)
    if n % 2 == 1:
        return float(merged[n // 2])
    else:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2

Complexity

  • Time Complexity: O((m + n) log(m + n)) – Sorting takes the most time.
  • Space Complexity: O(m + n) – Needs space for the merged list.

Efficiency Notes

Sorting wastes time since the arrays are already sorted. It’s too slow for the problem’s speed goal.

Solution 2: Merge Up to Median

Explanation

Since the arrays are sorted, we can merge them step by step with pointers and stop at the median spot(s), saving space by not making a full list.

  1. Determine Median Positions.
  • Figure out which spots we need: total length total = m + n. Odd needs the (total // 2 + 1)-th spot (1-based); even needs the (total // 2)-th and (total // 2 + 1)-th.

2. Merge with Pointers.

  • Merge by picking the smaller number each time, stopping when we hit the median spot(s).

3. Compute Median.

  • Use the last number (odd) or average the last two (even).

Step-by-Step Example

Example 1: nums1 = [1, 2], nums2 = [3, 4], total length = 4

We have nums1 = [1, 2] and nums2 = [3, 4], totaling 4 numbers. Since 4 is even, the median is the average of the 2nd and 3rd numbers.

  • Goal: Find the 2nd and 3rd numbers when merged, then average them.
  • Result for reference: Merged is [1, 2, 3, 4], 2nd is 2, 3rd is 3, median is (2 + 3) / 2 = 2.5.
  • Start: Use pointers i = 0 for nums1, j = 0 for nums2, count at 0.
  • Step 1: Compare nums1[0] = 1 and nums2[0] = 3. Pick 1. Set curr = 1, move i to 1, count is 1.
    • Keeps the order by choosing the smallest.
  • Step 2: Compare nums1[1] = 2 and nums2[0] = 3. Pick 2. Save prev = 1, set curr = 2, move i to 2, count is 2.
    • Saving the last number helps for averaging.
  • Step 3: nums1 done, pick nums2[0] = 3. Save prev = 2, set curr = 3, move j to 1, count is 3.
    • Switch arrays and stop at the 3rd number.
  • Result: 2nd number is 2 (prev), 3rd is 3 (curr). Average: (2 + 3) / 2 = 2.5.
    • Matches the median without merging everything.

Example 2: nums1 = [1, 3], nums2 = [2], total length = 3

Now, nums1 = [1, 3] and nums2 = [2] total 3 numbers. Since 3 is odd, the median is the 2nd number.

  • Goal: Find the 2nd number when merged.
  • Result for reference: Merged is [1, 2, 3], 2nd is 2, median is 2.0.
  • Start: i = 0, j = 0, count at 0.
  • Step 1: Compare nums1[0] = 1 and nums2[0] = 2. Pick 1. Set curr = 1, move i to 1, count is 1.
    • Gets us closer to the middle.
  • Step 2: Compare nums1[1] = 3 and nums2[0] = 2. Pick 2. Set curr = 2, move j to 1, count is 2.
    • 2nd number reached, stop for odd length.
  • Result: 2nd number is 2 (curr), median is 2.0.
    • Matches the middle of [1, 2, 3].

Code

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    m, n = len(nums1), len(nums2)
    total = m + n
    mid1 = total // 2
    mid2 = mid1 - 1 if total % 2 == 0 else mid1

    i = j = 0
    count = 0
    prev = curr = 0

    while count <= mid1 and (i < m or j < n):
        prev = curr
        if i < m and (j >= n or nums1[i] <= nums2[j]):
            curr = nums1[i]
            i += 1
        else:
            curr = nums2[j]
            j += 1
        count += 1

    if total % 2 == 1:
        return float(curr)
    return (prev + curr) / 2

Complexity

  • Time Complexity: O(m + n) – Merges up to the median.
  • Space Complexity: O(1) – Uses only a few variables.

Efficiency Notes

It’s smarter than brute force but still linear, not meeting the logarithmic goal.

Solution 3: Binary Search on Partition (Optimal)

Explanation

This method splits both arrays into left and right halves so the median sits at the boundary, using binary search on the smaller array to find the split fast.

  1. Setup.
  • Swap if nums1 is larger, search on the smaller one. Left half size = (m + n + 1) // 2.

2. Binary Search on nums1.

  • Guess a split point, adjust based on order, use ±∞ for edges.

3. Validate Partition.

  • Check if left numbers are less than or equal to right ones.

4. Compute Median.

  • Odd: Biggest left number; even: average of biggest left and smallest right.

Step-by-Step Example

Example 1: nums1 = [1, 3], nums2 = [2], total length = 3

We have nums1 = [1, 3] (m = 2) and nums2 = [2] (n = 1), totaling 3. Median is the 2nd number.

  • Goal: Split so left half has 2 numbers, median is the biggest left.
  • Result for reference: Merged is [1, 2, 3], 2nd is 2, median is 2.0.
  • Start: Search on nums1, range 0 to 2, left size 2.
  • Try split: Pick 1 for nums1, so 1 for nums2.
    • nums1: [1] | [3], nums2: [2] | [].
    • Left: 1, 2. Right: 3.
  • Check: Left 1 ≤ right 3, left 2 ≤ right 3. Works.
    • Split matches merged order.
  • Result: Odd, biggest left is max(1, 2) = 2, median is 2.0.
    • Matches the 2nd number.

Example 2: nums1 = [1, 2], nums2 = [3, 4], total length = 4

Now, nums1 = [1, 2] (m = 2) and nums2 = [3, 4] (n = 2) total 4. Median is the average of 2nd and 3rd.

  • Goal: Split into 2 and 2, average biggest left and smallest right.
  • Result for reference: Merged is [1, 2, 3, 4], 2nd is 2, 3rd is 3, median is (2 + 3) / 2 = 2.5.
  • Start: Search on nums1, range 0 to 2, left size 2.
  • Try split: Pick 1 for nums1, 1 for nums2.
    • nums1: [1] | [2], nums2: [3] | [4].
    • Left: 1, 3. Right: 2, 4.
  • Check: Left 1 ≤ right 2, left 3 ≤ right 2 (false). Adjust.
    • Too many big numbers left, take more from nums1.
  • New split: 2 for nums1, 0 for nums2.
    • nums1: [1, 2] | [], nums2: [] | [3, 4].
    • Left: 1, 2. Right: 3, 4.
  • Check: Left 1 ≤ right 3, left 2 ≤ right 3. Works.
    • Matches merged order.
  • Result: Even, average max left (2) and min right (3): (2 + 3) / 2 = 2.5.
    • Correct median.

Code

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

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

    low, high = 0, m
    while low <= high:
        partition1 = (low + high) // 2
        partition2 = total_left - partition1

        left1 = nums1[partition1 - 1] if partition1 > 0 else float('-inf')
        right1 = nums1[partition1] if partition1 < m else float('inf')
        left2 = nums2[partition2 - 1] if partition2 > 0 else float('-inf')
        right2 = nums2[partition2] if partition2 < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            high = partition1 - 1
        else:
            low = partition1 + 1

    return 0.0  # Unreachable

Complexity

  • Time Complexity: O(log(min(m, n))) – Binary search is fast.
  • Space Complexity: O(1) – No extra space.

Efficiency Notes

This meets the logarithmic goal, using the sorted order cleverly.

Additional Example

For nums1 = [1, 4, 7], nums2 = [2, 3, 5, 6], total = 7:

  • Goal: Left has 4, median is max left.
  • Reference: [1, 2, 3, 4, 5, 6, 7], 4th is 4, median 4.0.
  • Split: 2 from nums1, 2 from nums2.
    • Left: 1, 4, 2, 3. Right: 7, 5, 6.
  • Check: Works. Result: 4.0.

Edge Cases

  • Empty: nums1 = [], nums2 = [1] – Handled fine.
  • Equal: nums1 = [1, 1], nums2 = [1, 1] – Median 1.0.

Final Thoughts

  • Brute Force: Easy but slow.
  • Merge Up to Median: Smarter but not fast enough.
  • Binary Search: Tricky but perfect for speed.