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.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
The description was taken from https://leetcode.com/problems/median-of-two-sorted-arrays/.
#O(Log(M+N)) Time, O(1) Space
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums2) < len(nums1):
return self.findMedianSortedArrays(nums2, nums1)
total_len = len(nums1) + len(nums2)
half_len = total_len // 2
is_even = total_len % 2 == 0
left, right = 0, len(nums1) - 1
while True:
one_mid = (left + right) // 2
two_mid = half_len - one_mid - 2
one_left, one_right = float("-inf"), float("inf")
two_left, two_right = float("-inf"), float("inf")
if one_mid >= 0:
one_left = nums1[one_mid]
if one_mid + 1 < len(nums1):
one_right = nums1[one_mid + 1]
if two_mid >= 0:
two_left = nums2[two_mid]
if two_mid + 1 < len(nums2):
two_right = nums2[two_mid + 1]
if one_left <= two_right and one_right >= two_left:
if is_even:
return (max(one_left, two_left) + min(one_right, two_right))/2
else:
return min(one_right, two_right)
if one_left > two_right:
right = one_mid - 1
else:
left = one_mid + 1
Without merging and sorting these two lists, we can solve this by finding the intersection of the bisections of both lists.
What this means is we can have a left and right pointer for both lists and once the left pointer from the first list is less than or equal to the right pointer from the second list, and the right pointer from the first list is greater than or equal to the left pointer from the second list, we have found an intersection of bisections from both lists and can calculate the median from the current values.
First off, we are going to be calculating the middle pointer of the smaller list and then basing the middle pointer of the larger list based on that.
We don't want to do it the other way around because if for example, the larger list is twice the size as the smaller one then the middle value would be out of bounds.
Let's make it so that the smaller list is nums1 by re-running the function with the inputs switched if nums1 is larger.
if len(nums2) < len(nums1):
return self.findMedianSortedArrays(nums2, nums1)
Let's create some variables to make things easier for us.
We will want the total length of both arrays, the average of that, and whether the median is going to be even.
total_len = len(nums1) + len(nums2)
half_len = total_len // 2
is_even = total_len % 2 == 0
After that, we will set the initial left and right pointers to the beginning and end of the first list.
left, right = 0, len(nums1) - 1
Let's begin our binary search.
While we haven't returned anything, we will continue our search. The description says the answer is guaranteed to exist so we can run this loop indefinitely until we have found the median.
while True:
We will start by setting a middle pointer for nums one from the mean of the left and right pointers.
one_mid = (left + right) // 2
Then, we will set a middle pointer for nums two by subtracting the other list's middle pointer by the average of both list's lengths, minus two since both arrays have indices that begin at zero.
By basing the middle pointer of the larger list off of the middle pointer of the smaller list, this will allow us to only move left and right pointers for the smaller list to reduce our search space within each iteration.
two_mid = half_len - one_mid - 2
In the event that a bisection has reached the end of its respective list, we will want to initialize its value to infinity or negative infinity so that we don't get an index out of bounds error.
The condition for knowing whether we found a median is if we found an intersection where the left pointer from the first list is less than or equal to the right pointer from the second list, and the right pointer from the first list is greater than or equal to the left pointer from the second list.
To keep this condition intact when one of the pointers has gone out of bounds, we will set the initial left pointers to negative infinity and right pointers to positive infinity so that a left pointer can be less than positive infinity and a right pointer can be greater than negative infinity.
one_left, one_right = float("-inf"), float("inf")
two_left, two_right = float("-inf"), float("inf")
Then, we will overwrite these initial places if the middle pointers are in bounds.
We are calling these mid, but these are actually just the bisect indices, so the left pointer will be on the bisect and the right pointer will be one index past it.
if one_mid >= 0:
one_left = nums1[one_mid]
if one_mid + 1 < len(nums1):
one_right = nums1[one_mid + 1]
if two_mid >= 0:
two_left = nums2[two_mid]
if two_mid + 1 < len(nums2):
two_right = nums2[two_mid + 1]
If we have found a bisection intersection, and the total element count is even, then we will need to take a mean.
We will return the maximum left pointer plus the minimum right pointer divided by two. This will allow us to exclude infinite values.
if one_left <= two_right and one_right >= two_left:
if is_even:
return (max(one_left, two_left) + min(one_right, two_right))/2
If the count is odd, then we will return the minimum of the right pointers, again to exclude infinite values.
else:
return min(one_right, two_right)
If we didn't return anything then we will continue looking for the intersection.
If the left pointer of the first list is greater than the right pointer of the second list, then we need to slide the first list's bisection to the left.
if one_left > two_right:
right = one_mid - 1
Otherwise, we will need to slide it to the right.
else:
left = one_mid + 1