π Problem Details
- Title:
4. Median of Two Sorted Arrays
- Link: https://leetcode.com/problems/median-of-two-sorted-arrays/
- Difficulty: Hard
- Tags/Categories: Binary-Search
πWhat Were My Initial Thoughts?
- naive / brute force would be a merge-and-find approach which is linear in time O(n+m) (this is not efficient enough for the constraints of the question)
- a logarithmic time complexity suggests a binary search approach
- what is the trick to find the median without merging with the help of binary search
- the mid point of our first calculation in a single array finds the "median"
- how can we apply this rule to our separate subarrays
Key Idea:
- suppose we merge
nums1
andnums2
into a single sorted array of lengthx = n+m
- the median is the element at index
x/2
(or the average of the two middle elements ifx
is even) - instead of merging, we only need to retrieve the first
x/2
elements from both arrays combined - we can achieve this by using binary search on the smaller array to determine how many elements should come from each array
π‘ Explanation of Solution
1. Partitioning Condition
- we need to divide nums1 and nums2 such that:
- the left half contains x/2 smallest elements
- the right half contains the remaining elements
- we determine a partition index i in nums1, which means taking i elements from nums1
- the remaining x/2-i elements must come from nums2
2. Finding the Correct Partition
- we adjust i (the partition index in nums1) using binary search to satisfy:
- nums1[i - 1] β€ nums2[j] (ensuring the left half is correctly partitioned)
- nums2[j - 1] β€ nums1[i] (ensuring the right half is correctly partitioned)
- if nums1[i - 1] > nums2[j] , it means we took too many elements from nums1, so we move left
- if nums2[j - i] > nums1[i] , it means we took too few elements from nums1, so we move right
3. Extracting the Median
- if x is odd: the largest element is in the left half
- max(nums1[i - 1], nums2[j - 1])
- if x is even: the largest element is the average of the largest element in the left half and the smallest element in the right half
- (max(nums1[i - 1], nums2[j - 1]) + min(nums1[i], nums2[j])) / 2
β Complexity Analysis
Time Complexity: O(log N)
Space Complexity: O(1)
π» Implementation of Solution
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// ensure nums1 is the smaller array
if(nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
int n = nums1.size();
int m = nums2.size();
int left = 0;
int right = n;
int half = (n + m + 1) / 2; // the smallest x/2 elements
while(left <= right) {
int i = left + (right - left) / 2; // partition index in nums1
int j = half - i; // partition index in nums 2
// boundary conditions
int leftMax1 = (i == 0) ? INT_MIN : nums1[i - 1];
int rightMin1 = (i == n) ? INT_MAX : nums1[i];
int leftMax2 = (j == 0) ? INT_MIN : nums2[j - 1];
int rightMin2 = (j == m) ? INT_MAX : nums2[j];
// valid partition found
if(leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
if((n+m) % 2 == 0) {
return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2.0;
} else {
return max(leftMax1, leftMax2);
}
}
// adjust binary search range
else if (leftMax1 > rightMin2) {
right = i - 1; // move left
} else {
left = i + 1; // move right
}
}
return -1;
}
};