LeetCode #4 – Median of Two Sorted Arrays

Problem Statement

1. Task


• You are 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:
  • nums1 = [1, 3], nums2 = [2]
  • Merged: [1, 2, 3]
  • Median: 2.0
• Example 2:
  • nums1 = [1, 2], nums2 = [3, 4]
  • Merged: [1, 2, 3, 4]
  • Median: (2 + 3) / 2 = 2.5

Naive vs. Optimal Approach

1. Naive Idea


• Merge the two arrays into one sorted array, then pick the middle element(s).
• Time complexity: O(m + n) (too slow for the required O(log(m + n))).


2. Optimal Idea: Binary Search on Partitions


• We do a binary search on a partition of the smaller array.
• We choose a cut position partition1 in nums1, and the corresponding cut position partition2 in nums2 is determined so that the left half of the combined arrays has the same number of elements as the right half (or one more when total length is odd).
• We want:
  • Every element on the left side of the combined partition to be ≤ every element on the right side.
  • This boils down to two inequalities:
    • maxLeft1 ≤ minRight2
    • maxLeft2 ≤ minRight1
• Once we find such a partition, the median is determined by the max of left side and min of right side.

Binary Search Partition Solution (TypeScript)

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const m = nums1.length;
    const n = nums2.length;

    // We always do binary search on the smaller array.
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }

    // We look for the partition in `nums1`, then the partition in `nums2` will solve itself naturally.
    // `l` and `r` are exactly used for locating the partition line in `nums1`.
    let l = 0;
    let r = m;

    while (1) {
        // `partition{1|2}` combined is the total count of the elements in the left part of the merged array.
        // #(left part of the merged array) >= #(right ...)
        let partition1 = Math.floor((l + r) / 2);
        let partition2 = Math.floor((m + n + 1) / 2) - partition1;

        let maxLeft1  = (partition1 === 0) ? -Infinity : nums1[partition1 - 1];
        let minRight1 = (partition1 === m) ?  Infinity : nums1[partition1];

        let maxLeft2  = (partition2 === 0) ? -Infinity : nums2[partition2 - 1];
        let minRight2 = (partition2 === n) ?  Infinity : nums2[partition2];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            const maxLeft  = (maxLeft1 > maxLeft2) ? maxLeft1 : maxLeft2;
            const minRight = (minRight1 < minRight2) ? minRight1 : minRight2;

            if ((m + n) % 2 === 0) {
                return (maxLeft + minRight) / 2;
            } else {
                return maxLeft;
            }
        }

        if (maxLeft1 > minRight2) {
            r -= 1;
        }

        if (maxLeft2 > minRight1) {
            l += 1;
        }
    }
};

const solution1 = findMedianSortedArrays;

export {};

• We ensure nums1 is the smaller array, so the binary search space is minimized.
• partition1 chooses how many elements go to the left side from nums1.
• partition2 is then forced so that the left side has exactly (m + n + 1) / 2 elements in total.
• maxLeft1, minRight1, maxLeft2, and minRight2 represent the border elements around the partition.
• We use -Infinity and Infinity to handle edge cases where the partition is at the extreme ends of an array.

Partition Intuition with Example

Example: nums1 = [1, 3], nums2 = [2, 4, 5].

• Total length: m + n = 5 (odd).
• We want left side to contain (5 + 1) / 2 = 3 elements.

• Now left side elements are [1, 3, 2] (not sorted individually, but the combined ordering is correct).
• Since total length is odd, median is max(maxLeft1, maxLeft2) = max(3, 2) = 3.

Complexity

• We perform a binary search over the smaller array nums1 of length m.
• Each step does O(1) work (constant number of comparisons and arithmetic).
• Time complexity: O(log m), and since m ≤ n, this is O(log(m + n)).
• Space complexity: O(1) extra space.