Median of Two Sorted Arrays

Solutions

Binary Search

Time: O(log(min(m,n)))Space: O(1)

We use binary search to find the partition point for both arrays. The idea is to partition both arrays such that elements on the left side of the partition are less than the elements on the right side. We calculate the max element on the left side and the min element on the right side. If the max element on the left side is less than or equal to the min element on the right side, we have found the correct partition. If the total number of elements is even, the median is the average of the max element on the left side and the min element on the right side. If the total number of elements is odd, the median is the max element on the left side.

function findMedianSortedArrays(nums1, nums2) {
  let m = nums1.length,
    n = nums2.length;
  if (m > n) return findMedianSortedArrays(nums2, nums1);
  let low = 0,
    high = m;
  while (low <= high) {
    let partitionX = Math.floor((low + high) / 2);
    let partitionY = Math.floor((m + n + 1) / 2) - partitionX;
    let maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
    let minRightX = partitionX === m ? Infinity : nums1[partitionX];
    let maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
    let minRightY = partitionY === n ? Infinity : nums2[partitionY];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 0)
        return (
          (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2
        );
      else return Math.max(maxLeftX, maxLeftY);
    } else if (maxLeftX > minRightY) high = partitionX - 1;
    else low = partitionX + 1;
  }
}

Constraints:

Examples:

Solutions

Binary Search

Follow-up: