Median of Two Sorted Arrays

Problem

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:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

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

Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const l1 = nums1.length > nums2.length ? nums2 : nums1; // smaller array
    const s1 = l1.length; // l1 size
    const l2 = nums1.length > nums2.length ? nums1 : nums2; // larger array
    const s2 = l2.length; // l2 size

    // binary search on smaller array l1
    let lo = 0;
    let hi = l1.length;

    while (lo <= hi) {
        // partition l1 and l2 so each combined halves contain half the elements
        const cut1 = (lo + hi) >> 1; // partition of l1
        const cut2 = ((s1 + s2 + 1) >> 1) - cut1; // partition of l2

        // find the four values directly before and after each partition
        const left1 = l1[cut1 - 1] ?? -Infinity; // max value in l1[:cut1]
        const right1 = l1[cut1] ?? Infinity; // min value in l1[cut1:]

        const left2 = l2[cut2 - 1] ?? -Infinity; // max value in l2[:cut2]
        const right2 = l2[cut2] ?? Infinity; // min value in l2[cut2:]

        // there exist element in left partition > right partition
        if (left1 > right2) { // need to make left1 smaller => try left half of l1
            hi = cut1 - 1;
        } else if (left2 > right1) { // need to make right1 larger => try on right half of l1
            lo = cut1 + 1;
        } else { // every element in left partition <= right partition
            if ((s1 + s2) % 2) { // odd number of elements
                return Math.max(left1, left2); // since left partition contains extra element
            } else { // even number of elements
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
            }
        }
    }
};

We will implement a binary search solution. Observe that if we partition nums1 and nums2 both into two halves, such that the combined size of the left partition is equal to the combined size of the right partition, and all values in the left partition is <= everything in the right partition, the median must be one (or two if there are an even number of elements) of the four values directly before and after the partition index.

For example, if nums1 = [x1, x2, x3] and nums2 = [y1, y2, y3]. A possible partition is [x1 | x2, x3] and [y1, y2 | y3] since the size of [x1, y1, y2] is equal to the size of [x2, x3, y3] (if there are an odd number of elements, we make the left partition have one extra value). Futhermore, if all values in the left partition is <= everything in the right partition, the median must be one or two of x1, x2, y2, y3.

Notice that once we determine the partition index of nums1, the partition index of nums2 is also determined. In other words, by finding the the partition index of nums1, we also get the partition index of nums2.

Thus, using the above observations, we can use binary search to find the correct partition index of either nums1 or nums2. For optimization purposes, we will use the array with the smaller size, as this gives us a runtime of O(log(min(m, n))). The algorithm works as follows:

Setup the standard binary search template using the array with the smaller size (say l1 is smaller and l2 is larger).
Use the partition index of l1 as the middle index (ie. (lo + hi) / 2) and find the corresponding partition index in l2 as per the above rules.
Find the four values directly before and after the partition index of l1 and l2.
Check how values in the left partition compares to the right partition:
- If the max value in the left partition of l1 is > than the min value in the right partition of l2, this must mean our partition index of l1 is to large, and so we reduce the search space to the left half of l1 and restart from step 2.
- If the max value in the left partition of l2 is > than the min value in the right partition of l1, this must mean our partition index of l1 is to small, and so we reduce the search space to the right half of l1 and restart from step 2.
- Otherwise, it must mean all elements in the left partition is >= all elements in the right partition, and so the median must be one or two of the values in step 3.

Note that for step 4, since l1 and l2 are both sorted, the two min values in the left partition are the two values directly before the partition index, and the two max values in the right partition are the two values directly after the partition index (ie. values computed in step 3). Futhermore, we don't need to compare the left and right partition from the same array, since they are sorted, and so the values in the left partition must be <= the right partition by definition.

Problem​

Solution​

Problem

Solution