0004. Median of Two Sorted Arrays
Hard | Binary Search | 80 ms (97.98%), 14.5 MB (81.46%)
Source: LeetCode - Median of Two Sorted Arrays GitHub: Solution / Performance
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))
.
At first, we find the total length of the merged array to understand how many elements are in the left and right parts respectively. size = (total_length + 1) // 2
Next, in each iteration, we take n
elements from nums1 and size - n
elements from nums2. l, r = 0, len(nums1)
n = (l + r) // 2
Then check whether selected elements are valid or not by comparing them with non-selected elements.
If valid, we return the median immediately. If not valid, we modify the search space.
p1 = (l + r) // 2
p2 = size - p1
nums1_left = float('-inf') if p1 == 0 else nums1[p1 - 1]
nums1_right = float('inf') if p1 == m else nums1[p1]
nums2_left = float('-inf') if p2 == 0 else nums2[p2 - 1]
nums2_right = float('inf') if p2 == n else nums2[p2]
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# ==================================================
# Array + Binary Seearch =
# ==================================================
# time : O(log(min(m,n)))
# space : O(1)
if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
total = m + n
size = (total + 1) // 2
l, r = 0, len(nums1)
while l <= r:
p1 = (l + r) // 2
p2 = size - p1
nums1_left = float('-inf') if p1 == 0 else nums1[p1 - 1]
nums1_right = float('inf') if p1 == m else nums1[p1]
nums2_left = float('-inf') if p2 == 0 else nums2[p2 - 1]
nums2_right = float('inf') if p2 == n else nums2[p2]
if nums1_left > nums2_right: r = p1 - 1
elif nums2_left > nums1_right: l = p1 + 1
else:
if total & 1: return max(nums1_left, nums2_left)
return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
Last updated
Was this helpful?