Median of Two Sorted Arrays

Median of Two Sorted Arrays

Median of Two Sorted Arrays

Problem

You are given two sorted arrays, nums1 and nums2, of size m and n. Return the median of the two arrays.

The run time must be O(log(m + n)).

The median is the middle value of the merged sorted array.

• If the total size is odd, the median is the middle element.
• If the total size is even, the median is the average of the two middle elements.

Examples

Example 1

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

• The merged array is [1,2,3], and the median is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000

• The merged array is [1,2,3,4].
• The median is (2 + 3) / 2 = 2.5.

Solution 1: Merge and Sort (Simple)

We join both arrays, sort the result, and pick the middle value.

var findMedianSortedArrays = function (nums1, nums2) {
    const merged = [...nums1, ...nums2].sort((a, b) => a - b);
    const len = merged.length;
    const mid = Math.floor(len / 2);

    return len % 2 === 0
        ? (merged[mid - 1] + merged[mid]) / 2
        : merged[mid];
};

How the Code Works

• [...nums1, ...nums2] joins both arrays into one.
• sort((a, b) => a - b) sorts the numbers in increasing order.
• If the length is even, we average the two middle values.
• If the length is odd, we return the middle value.

Complexity

• Time Complexity: O((m + n) log(m + n))
  • Sorting the joined array is the biggest cost.
• Space Complexity: O(m + n)
  • The merged array holds all elements.

Important: This works, but it does not follow the problem rule of O(log(m + n)). Both input arrays are already sorted, and this solution does not use that fact.

Main Idea for the Optimal Solution

We do not need to merge the arrays. We only need to find the middle cut.

Imagine we split the merged array into a left half and a right half of equal size. The median depends only on the numbers next to the cut.

We make one cut in nums1 and one cut in nums2:

nums1:  [ ... l1 | r1 ... ]
nums2:  [ ... l2 | r2 ... ]

• l1 and l2 are the last elements on the left side of each cut.
• r1 and r2 are the first elements on the right side of each cut.

The cuts are correct when:

• The left side has the right number of elements: (m + n + 1) / 2 (rounded down).
• Every number on the left is smaller than or equal to every number on the right.

Each array is already sorted, so we only need to check two things:

• l1 <= r2
• l2 <= r1

Finding the median from a correct cut

• Odd total size: The median is the biggest number on the left side, max(l1, l2).
• Even total size: The median is the average of the biggest left number and the smallest right number: (max(l1, l2) + min(r1, r2)) / 2.

Using binary search

We only choose the cut in nums1. The cut in nums2 is then fixed:

cut2 = half - cut1

Here half = floor((m + n + 1) / 2). So we binary search over cut1 from 0 to m.

• If l1 > r2, we took too many elements from nums1. Move the cut left: high = cut1 - 1.
• If l2 > r1, we took too few elements from nums1. Move the cut right: low = cut1 + 1.
• Otherwise, the cut is correct.

Handling the edges

A cut can be at the very start or the very end of an array.

• If a cut is at the start, there is no left element. We use -Infinity.
• If a cut is at the end, there is no right element. We use Infinity.

These values never break the comparisons.

Why we search the smaller array

cut2 = half - cut1 must stay between 0 and n. This is always true when nums1 is the smaller array. So if nums1 is bigger, we swap the two arrays. It also makes the search faster.

Solution 2: Binary Search on the Cut (Optimal)

var findMedianSortedArrays = function (nums1, nums2) {
    // always search in the smaller array
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    const m = nums1.length;
    const n = nums2.length;

    // number of elements on the left side
    const half = Math.floor((m + n + 1) / 2);

    let low = 0;
    let high = m;

    while (low <= high) {
        // how many elements we take from each array
        const cut1 = Math.floor((low + high) / 2);
        const cut2 = half - cut1;

        // elements around the cuts
        const l1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
        const l2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
        const r1 = cut1 === m ? Infinity : nums1[cut1];
        const r2 = cut2 === n ? Infinity : nums2[cut2];

        if (l1 <= r2 && l2 <= r1) {
            // correct cut
            if ((m + n) % 2 === 1) {
                return Math.max(l1, l2);
            }
            return (Math.max(l1, l2) + Math.min(r1, r2)) / 2;
        } else if (l1 > r2) {
            // too many elements from nums1, move left
            high = cut1 - 1;
        } else {
            // too few elements from nums1, move right
            low = cut1 + 1;
        }
    }
};

How the Code Works

Step 1: Pick the smaller array

• If nums1 is longer, we call the function again with the arrays swapped.
• Now nums1 is always the smaller one.

Step 2: Find half

• half = floor((m + n + 1) / 2) is the size of the left side.
• Using + 1 makes the left side hold the extra element when the total is odd. So for an odd total, the median is on the left side.

Step 3: Binary search on cut1

• cut1 is how many elements we take from nums1 for the left side.
• cut2 = half - cut1 is how many we take from nums2.

Step 4: Find the four border values

• l1 and l2 are the last elements of the left side.
• r1 and r2 are the first elements of the right side.
• We use -Infinity and Infinity when a cut is at the edge of an array.

Step 5: Check the cut

• l1 <= r2 and l2 <= r1: The cut is correct. We calculate the median.
• l1 > r2: nums1 gave too many elements. We search the left part.
• Otherwise: nums1 gave too few elements. We search the right part.

Dry Run

Let us take nums1 = [1, 3] and nums2 = [2].

nums1 is longer, so we swap. Now nums1 = [2] and nums2 = [1, 3].

Here m = 1, n = 2, and half = floor(4 / 2) = 2.

The total size is 3, which is odd. So the median is max(l1, l2) = max(2, 1) = 2.

Now let us take nums1 = [1, 2] and nums2 = [3, 4].

Here m = 2, n = 2, and half = 2.

The total size is 4, which is even. So the median is (max(2, -Inf) + min(Inf, 3)) / 2 = (2 + 3) / 2 = 2.5.

Complexity

• Time Complexity: O(log(min(m, n)))
  • We binary search only on the smaller array.
  • Each step takes O(1) time.
  • This is even better than the required O(log(m + n)).
• Space Complexity: O(1)
  • We use only a few variables.
  • The swap call returns right away, so it adds no extra depth.

Comparison

Summary

• The median splits the merged array into a left half and a right half.
• We do not merge. We only find a cut in each array so that the left side is the right size and all left values are <= all right values.
• We binary search the cut in the smaller array. The other cut follows from cut2 = half - cut1.
• We use -Infinity and Infinity for cuts at the edges.
• For an odd total, the median is max(l1, l2). For an even total, it is (max(l1, l2) + min(r1, r2)) / 2.
• Merge and sort is simple but too slow for the problem rule. Binary search runs in O(log(min(m, n))) time and uses O(1) space.