Median of Two Sorted Arrays

Published: Dec 9, 2022

Hard Binary Search Array

Problem Description

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))`.

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`

https://leetcode.com/problems/median-of-two-sorted-arrays/

Examples

``````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.
``````

How to Solve

An easy solution is: merge two arrays, sort it then return the middle value(s). However, the problem requires O(log(m + n)) time complexity, which suggests the binary search approach. The binary search indices will be based on the shorter array. The solution starts from the shorter array’s index, mid2 = (low + high) // 2, and the longer array’s index, mid1 = m + n - mid2. Next, values at four indices below are compared:

• nums1’s middle 2 indices – l1 (left), r1 (right)
• nums2’s middle 2 indices – l2 (left), r2 (right)

When l1 > r2, the median exists on the left half of nums1. So, the high value should be decreased. When l2 > r1, the median exists on the right half of nums1. So, the low value should be increased. Otherwise, the values for median were found. So, calculate and return the median.

Solution

``````class MedianOfTwoSortedArrays {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m < n) {
return findMedianSortedArrays(nums2, nums1);
}
if (n == 0) {
return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;
}
int low = 0, high = n * 2;
while (low <= high) {
int mid2 = (low + high) / 2;
int mid1 = m + n - mid2;
int l1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2];
int l2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2];
int r1 = mid1 == m * 2 ? INT_MAX : nums1[mid1 / 2];
int r2 = mid2 == n * 2 ? INT_MAX : nums2[mid2 / 2];
if (l1 > r2) {
low = mid2 + 1;
} else if (l2 > r1) {
high = mid2 - 1;
} else {
return ((l1 < l2 ? l2 : l1) + (r1 < r2 ? r1 : r2)) / 2.0;
}
}
return 0.0;
}
};
``````
``````
``````
``````
``````
``````class MedianOfTwoSortedArrays:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m < n:
return self.findMedianSortedArrays(nums2, nums1)
if n == 0:
return (nums1[(m - 1) // 2] + nums1[m // 2]) / 2.0

low, high = 0, n * 2
while low <= high:
mid2 = (low + high) // 2
mid1 = m + n - mid2
l1 = float('-inf') if mid1 == 0 else nums1[(mid1 - 1) // 2]
l2 = float('-inf') if mid2 == 0 else nums2[(mid2 - 1) // 2]
r1 = float('inf') if mid1 == m * 2 else nums1[mid1 // 2]
r2 = float('inf') if mid2 == n * 2 else nums2[mid2 // 2]
if l1 > r2:
low = mid2 + 1
elif l2 > r1:
high = mid2 - 1
else:
return (max([l1, l2]) + min([r1, r2])) / 2.0
``````
``````# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Float}

class Integer
N_BYTES = [42].pack('i').size
N_BITS = N_BYTES * 16
MAX = 2 ** (N_BITS - 2) - 1
MIN = -MAX - 1
end
INT_MIN = Integer::MIN
INT_MAX = Integer::MAX

def find_median_sorted_arrays(nums1, nums2)
m = nums1.length
n = nums2.length
return find_median_sorted_arrays(nums2, nums1) if m < n
return (nums1[(m - 1) / 2].to_f + nums1[m / 2].to_f) / 2 if n == 0

lo, hi = 0, n * 2
while lo <= hi do
mid2 = (lo + hi) / 2
mid1 = m + n - mid2
l1 = (mid1 == 0) ? INT_MIN : nums1[(mid1 - 1) / 2]
l2 = (mid2 == 0) ? INT_MIN : nums2[(mid2 - 1) / 2]
r1 = (mid1 == m * 2) ? INT_MAX : nums1[(mid1 / 2)]
r2 = (mid2 == n * 2) ? INT_MAX : nums2[(mid2 / 2)]
if l1 > r2
lo = mid2 + 1
elsif l2 > r1
hi = mid2 - 1
else
return ([l1, l2].max.to_f + [r1, r2].min.to_f) / 2
end
end
end
``````

Complexities

• Time: `O(log(m + n))` – m, n: lengths of two arrays
• Space: `O(1)`