Difficulty: Hard | Acceptance: 44.53% | Paid: No
Topics: Array, Binary Search, Divide and Conquer
- Examples
- Constraints
- Brute Force - Merge and Sort
- Optimal - Binary Search
- Alternative - Linear Time with Pointers
Examples
Input
nums1 = [1,3], nums2 = [2]
Output
2.00000
Explanation
merged array = [1,2,3] and median is 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
- 0 <= nums1[i], nums2[i] <= 10^6
Brute Force - Merge and Sort
Intuition
The most straightforward approach is to merge both sorted arrays into a single array and then compute the median. This approach is easy to understand and implement but is not optimal in terms of time and space complexity.
Steps
- Combine the two arrays into one.
- Sort the combined array.
- Calculate the median based on the length of the merged array.
def findMedianSortedArrays(nums1, nums2):
merged = sorted(nums1 + nums2)
n = len(merged)
if n % 2 == 1:
return float(merged[n // 2])
else:
return (merged[n // 2 - 1] + merged[n // 2]) / 2.0Complexity
- Time: O((m + n) log(m + n)) - Sorting the merged array takes this time.
- Space: O(m + n) - Extra space used for storing the merged array.
Optimal - Binary Search
Intuition
To achieve the optimal O(log(min(m, n))) complexity, we use a binary search approach. The key insight is to partition both arrays such that the left half contains the smaller elements and the right half the larger ones, maintaining the length property of a median.
Steps
- Use binary search to find the correct partition in the smaller array.
- Calculate the corresponding partition in the second array.
- Ensure that all elements to the left of the partitions are less than or equal to elements on the right.
- Compute and return the median based on the partition.
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
low, high = 0, x
while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 - partitionX
maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
minX = float('inf') if partitionX == x else nums1[partitionX]
maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minY = float('inf') if partitionY == y else nums2[partitionY]
if maxX <= minY and maxY <= minX:
if (x + y) % 2 == 0:
return (max(maxX, maxY) + min(minX, minY)) / 2
else:
return max(maxX, maxY)
elif maxX > minY:
high = partitionX - 1
else:
low = partitionX + 1Complexity
- Time: O(log(min(m, n))) - Binary search is performed on the smaller of the two arrays.
- Space: O(1) - Only a constant amount of additional space is used.
Alternative - Linear Time with Pointers
Intuition
If we traverse both arrays simultaneously with two pointers, we can find the median by reaching the middle elements without creating a new merged array. This approach uses O(1) space but has a longer time complexity compared to the binary search method.
Steps
- Initialize two pointers, one for each array.
- Traverse both arrays up to the index of the median.
- Keep track of the elements as we move through the arrays.
- Once we reach the median index (or indices), compute and return the median value.
def findMedianSortedArrays(nums1, nums2):
m, n = len(nums1), len(nums2)
total = m + n
i = j = 0
current = prev = 0
for _ in range(total // 2 + 1):
prev = current
if i < m and (j >= n or nums1[i] < nums2[j]):
current = nums1[i]
i += 1
else:
current = nums2[j]
j += 1
if total % 2 == 1:
return float(current)
else:
return (prev + current) / 2.0Complexity
- Time: O(m + n) - In the worst case, we might need to traverse almost all elements of both arrays.
- Space: O(1) - No extra space is used beyond variables for tracking indices and values.