Median of Two Sorted Arrays

Problem Description

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 steps should be O(log (m+n)).

Examples

Constraints

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

Binary Search on Partitions

To find the median in logarithmic time, we partition both arrays into two halves (left and right) such that:

1. The left half contains exactly (m + n + 1) / 2 elements.
2. Every element in the left half is less than or equal to every element in the right half. We can binary search the partition point in the smaller array nums1. Let the partition index in nums1 be i, and the corresponding partition index in nums2 be j = (m + n + 1) / 2 - i. Let:

• left1 = nums1[i-1] and right1 = nums1[i]
• left2 = nums2[j-1] and right2 = nums2[j] A partition is valid if left1 <= right2 and left2 <= right1.
• If left1 > right2, we partitioned too far right in nums1; we shift our search left.
• If left2 > right1, we partitioned too far left in nums1; we shift our search right. Once valid, the median is computed from the maximum of the left elements and minimum of the right elements.

Solution 1: Partition Binary Search

Binary search the partition boundary in the smaller array to find the median.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1); // ensure nums1 is smaller
        }

        int left = 0;
        int right = m;
        int halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = halfLen - i;

            int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (left1 <= right2 && left2 <= right1) {
                // Odd elements count
                if ((m + n) % 2 != 0) {
                    return Math.max(left1, left2);
                }
                // Even elements count
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
            } else if (left1 > right2) {
                right = i - 1; // shift left in nums1
            } else {
                left = i + 1; // shift right in nums1
            }
        }
        return 0.0;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)  # ensure nums1 is smaller
            
        left, right = 0, m
        half_len = (m + n + 1) // 2
        
        while left <= right:
            i = left + (right - left) // 2
            j = half_len - i
            
            left1 = float('-inf') if i == 0 else nums1[i - 1]
            right1 = float('inf') if i == m else nums1[i]
            left2 = float('-inf') if j == 0 else nums2[j - 1]
            right2 = float('inf') if j == n else nums2[j]
            
            if left1 <= right2 and left2 <= right1:
                # Odd elements count
                if (m + n) % 2 != 0:
                    return float(max(left1, left2))
                # Even elements count
                return (max(left1, left2) + min(right1, right2)) / 2.0
            elif left1 > right2:
                right = i - 1  # shift left
            else:
                left = i + 1  # shift right
                
        return 0.0

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int left = 0;
        int right = m;
        int halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = halfLen - i;

            int left1 = (i == 0) ? INT_MIN : nums1[i - 1];
            int right1 = (i == m) ? INT_MAX : nums1[i];
            int left2 = (j == 0) ? INT_MIN : nums2[j - 1];
            int right2 = (j == n) ? INT_MAX : nums2[j];

            if (left1 <= right2 && left2 <= right1) {
                if ((m + n) % 2 != 0) {
                    return std::max(left1, left2);
                }
                return (std::max(left1, left2) + std::min(right1, right2)) / 2.0;
            } else if (left1 > right2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return 0.0;
    }
};

Complexity Analysis

• Time Complexity: O(log(min(m, n))) since we perform binary search on the smaller array.
• Space Complexity: O(1) auxiliary space as we only use partition indicators.

Where It Breaks

If the inputs are stream lists that cannot be indexed in O(1) time (e.g. sorted linked lists), this partition calculations method fails.

Common Mistakes

• Incorrect check conditions: Forgetting to swap the arrays if m > n. If nums1 is larger, index j can become negative or exceed n, causing index out of bounds exceptions.
• Off-by-one errors on boundary values: Using nums1[i] instead of nums1[i - 1] to represent the left partition element.

Frequently Asked Questions

Why does ensure nums1 is smaller prevent array bounds exceptions? Because j = (m + n + 1) / 2 - i, if m <= n, then i can vary from 0 to m, ensuring that j is always in the valid range [0, n].

What represents INT_MIN and INT_MAX in Python? Python supports arbitrary precision integers, so we use float('-inf') and float('inf') to represent infinity bounds.

← All Problems