Problem
Given two sorted arrays nums1 and nums2, return the median of the two arrays.The overall time complexity should be O(log(m + n)), where m and n are the lengths of the two arrays.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
nums1 = [1,3]
nums2 = [2]Output
2.0Example 2
Input
nums1 = [1,2]
nums2 = [3,4]Output
2.5Solution
This solution uses the Binary Search pattern. Instead of merging the two arrays, we find a partition that divides the combined elements into two equal halves.We always perform binary search on the smaller array. For a partition in the first array, we calculate the corresponding partition in the second array so that the left side contains half of the total elements.
The correct partition is found when every element on the left side is less than or equal to every element on the right side. Once the correct partition is found, the median can be calculated from the boundary elements.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Always binary search on the smaller array.
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0;
int right = m;
while (left <= right) {
int partition1 = (left + right) / 2;
int partition2 = (m + n + 1) / 2 - partition1;
int left1 = partition1 == 0
? Integer.MIN_VALUE
: nums1[partition1 - 1];
int right1 = partition1 == m
? Integer.MAX_VALUE
: nums1[partition1];
int left2 = partition2 == 0
? Integer.MIN_VALUE
: nums2[partition2 - 1];
int right2 = partition2 == n
? Integer.MAX_VALUE
: nums2[partition2];
// Correct partition found.
if (left1 <= right2 && left2 <= right1) {
// Total number of elements is even.
if ((m + n) % 2 == 0) {
return (Math.max(left1, left2)
+ Math.min(right1, right2)) / 2.0;
}
// Total number of elements is odd.
return Math.max(left1, left2);
}
// Move partition in nums1 to the left.
if (left1 > right2) {
right = partition1 - 1;
} else {
// Move partition in nums1 to the right.
left = partition1 + 1;
}
}
return 0.0;
}
}Complexity
Binary search is performed on the smaller array, so the time complexity isO(log(min(m, n))), where m and n are the lengths of the two arrays.
The solution uses only a few variables, so the extra space complexity is
O(1).