Median of Two Sorted Arrays

Median of Two Sorted Arrays: 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^6 <= nums1[i], nums2[i] <= 10^6

Try this Problem on your own or check similar problems:

Median of a Row Wise Sorted Matrix

Solution:

Java
JavaScript
Python
C++

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  if (nums1.length > nums2.length) {
      return findMedianSortedArrays(nums2, nums1);
  }

  int m = nums1.length;
  int n = nums2.length;
  int low = 0;
  int high = m;

  while (low <= high) {
    int partitionX = low + (high - low) / 2;
    int partitionY = (m + n + 1) / 2 - partitionX;

    int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
    int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];
    int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
    int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];

    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
        if ((m + n) % 2 == 0) {
          return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
        } else {
          return (double)Math.max(maxLeftX, maxLeftY);
        }
    } else if (maxLeftX > minRightY) {
      high = partitionX - 1;
    } else {
      low = partitionX + 1;
    }
  }

  return 0.0;
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  let m = nums1.length;
  let n = nums2.length;
  let low = 0;
  let high = m;

  while (low <= high) {
    let partitionX = low + Math.floor((high - low) / 2);
    let partitionY = Math.floor((m + n + 1) / 2) - partitionX;

    let maxLeftX =
      partitionX === 0 ? Number.MIN_SAFE_INTEGER : nums1[partitionX - 1];
    let minRightX =
      partitionX === m ? Number.MAX_SAFE_INTEGER : nums1[partitionX];
    let maxLeftY =
      partitionY === 0 ? Number.MIN_SAFE_INTEGER : nums2[partitionY - 1];
    let minRightY =
      partitionY === n ? Number.MAX_SAFE_INTEGER : 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;
    }
  }

  return 0.0;
};

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)

        m = len(nums1)
        n = len(nums2)
        low = 0
        high = m

        while low <= high:
            partitionX = low + (high - low) // 2
            partitionY = (m + n + 1) // 2 - partitionX

            maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
            minRightX = float('inf') if partitionX == m else nums1[partitionX]
            maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
            minRightY = float('inf') if partitionY == n else nums2[partitionY]

            if maxLeftX <= minRightY and maxLeftY <= minRightX:
                if (m + n) % 2 == 0:
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
                else:
                    return max(maxLeftX, maxLeftY)
            elif maxLeftX > minRightY:
                high = partitionX - 1
            else:
                low = partitionX + 1

        return 0.0

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size();
        int n = nums2.size();
        int low = 0;
        int high = m;

        while (low <= high) {
            int partitionX = low + (high - low) / 2;
            int partitionY = (m + n + 1) / 2 - partitionX;

            int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
            int minRightX = (partitionX == m) ? INT_MAX : nums1[partitionX];
            int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
            int minRightY = (partitionY == n) ? INT_MAX : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((m + n) % 2 == 0) {
                    return (double)(max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
                } else {
                    return (double)max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        return 0.0;
    }
};

Time/Space Complexity:

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

Explanation:

The algorithm begins by checking which of the two arrays is shorter and swapping them if necessary to ensure that nums1 is the shorter of the two arrays. This is done to ensure that the time complexity of the algorithm is O(log(min(m, n))), where m and n are the lengths of the two arrays.

Next, the algorithm uses a binary search-like approach to partition the two arrays and search for the median. It does this by maintaining four variables: low, high, partitionX, and partitionY. low and high represent the beginning and end indices of the search range in nums1, and partitionX represents the index of the partition point in nums1. partitionY is then calculated as (m + n + 1) / 2 - partitionX, where m is the length of nums1 and n is the length of nums2. This ensures that the combined length of the two partitions is equal to the total length of the two arrays.

The algorithm then compares the elements at the partition points in the two arrays. If the maximum element in the left partition of nums1 is less than or equal to the minimum element in the right partition of nums2, and the maximum element in the left partition of nums2 is less than or equal to the minimum element in the right partition of nums1, then the median must be in one of these partitions. If the total length of the two arrays is even, then the median is the average of the maximum element in the left partition and the minimum element in the right partition. If the total length is odd, then the median is the maximum element in the left partition.

If the maximum element in the left partition of nums1 is greater than the minimum element in the right partition of nums2, then the median must be in the left half of nums1 or the right half of nums2. In this case, the algorithm updates low to partitionX + 1 and high to partitionX - 1 and goes back to the beginning of the loop.

If the maximum element in the left partition of nums1 is less than the maximum element in the left partition of nums2, then the median must be in the right half of nums1 or the left half of nums2. In this case, the algorithm updates low to partitionX + 1 and high to partitionX - 1 and goes back to the beginning of the loop.

The algorithm repeats this process until low is greater than high, at which point it returns the median as the result.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​