Median of Two Sorted Arrays

Problem Statement

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.

Approach: Binary Search on the Smaller Array

Finding the median of two sorted arrays is equivalent to partitioning both arrays into a single left half and a single right half such that:

1. Both halves have an equal number of elements (or the left half has one more if the total number of elements is odd).
2. Every element in the left half is less than or equal to every element in the right half.

Instead of merging the arrays, we can run a Binary Search on the smaller array to find the correct partition point. By ensuring we binary search on the smaller array, we guarantee $O(\log(\min(m, n)))$ time complexity.

1. Let A be the smaller array and B be the larger array (swap nums1 and nums2 if nums1.length > nums2.length).
2. Let $m$ be the length of A and $n$ be the length of B. The total number of elements in the left half is $half = \lfloor \frac{m + n + 1}{2} \rfloor$.
3. We set our binary search bounds on A: left = 0 and right = m.
4. While left <= right, we calculate the partition index i in A:
   • i = Math.floor((left + right) / 2)
   • The partition index j in B is forced to be: j = half - i.
5. We look at the elements directly on the left and right of these partitions:
   • Aleft: The largest element on the left side of A (use $-\infty$ if i === 0).
   • Aright: The smallest element on the right side of A (use $\infty$ if i === m).
   • Bleft: The largest element on the left side of B (use $-\infty$ if j === 0).
   • Bright: The smallest element on the right side of B (use $\infty$ if j === n).
6. Check if the partition is valid. It’s valid if all elements on the left are $\le$ all elements on the right. This means Aleft <= Bright and Bleft <= Aright.
   • If valid:
     • If the total number of elements is odd, the median is Math.max(Aleft, Bleft).
     • If the total number of elements is even, the median is (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.
   • If invalid:
     • If Aleft > Bright, we have too many elements from A on the left. We must move our partition i to the left: right = i - 1.
     • Otherwise, Bleft > Aright. We need more elements from A on the left: left = i + 1.

Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function findMedianSortedArrays(nums1, nums2) {
    let A = nums1;
    let B = nums2;
    
    // Always run binary search on the smaller array to guarantee O(log(min(m, n)))
    if (A.length > B.length) {
        let temp = A;
        A = B;
        B = temp;
    }
    
    const m = A.length;
    const n = B.length;
    let left = 0;
    let right = m;
    const half = Math.floor((m + n + 1) / 2);
    
    while (left <= right) {
        const i = Math.floor((left + right) / 2); // partition in A
        const j = half - i;                       // partition in B
        
        const Aleft = i === 0 ? -Infinity : A[i - 1];
        const Aright = i === m ? Infinity : A[i];
        
        const Bleft = j === 0 ? -Infinity : B[j - 1];
        const Bright = j === n ? Infinity : B[j];
        
        // Partition is correct
        if (Aleft <= Bright && Bleft <= Aright) {
            // Odd total length
            if ((m + n) % 2 !== 0) {
                return Math.max(Aleft, Bleft);
            }
            // Even total length
            return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0;
        } 
        // Aleft is too big, partition in A must move left
        else if (Aleft > Bright) {
            right = i - 1;
        } 
        // Aright is too small, partition in A must move right
        else {
            left = i + 1;
        }
    }
    
    return 0; // Should never reach here if inputs are valid arrays
}

Complexity Analysis

• Time Complexity: $O(\log(\min(m, n)))$ where $m$ and $n$ are the lengths of the two arrays. By swapping the arrays to ensure we always perform binary search on the smaller array, the search space is at most $\min(m, n)$.
• Space Complexity: $O(1)$. We are only using a few pointers and variables to keep track of indices and bounds, requiring constant extra space.