4. Median of Two Sorted Arrays
Problem Statement
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.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Intuition
Links
Video Links
Approach 1:
Brute:
NlogN time and 1 Space
Directly Inserted one array in other and used sort
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
nums1.insert(nums1.end(), nums2.begin(), nums2.end());
sort(nums1.begin(), nums1.end());
int n = nums1.size();
if(n == 0) return 0;
int idx = n/2;
if(n%2 == 0)
return (nums1[idx]+nums1[idx-1])/2.0;
return nums1[idx];
}
};
Approach 2:
Merge Algorithm
m+n time and m+n space
Merged two sorted using pointers in other array
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> arr;
int i=0, j=0;
while(i<nums1.size() and j<nums2.size()){
if(nums1[i] < nums2[j])
arr.push_back(nums1[i++]);
else
arr.push_back(nums2[j++]);
}
while(i<nums1.size())
arr.push_back(nums1[i++]);
while(j<nums2.size())
arr.push_back(nums2[j++]);
int index = arr.size()/2;
if(arr.size() % 2 == 0)
return (arr[index] + arr[index-1]) / 2.0;
return arr[index];
}
};
Approach 3:
Merge Algorithm optimised
m+n time and 1 space
Maintained variables to keep track of index
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int i=0, j=0;
int count = 0;
int idx1 = (m+n)/2;
int idx2 = idx1-1;
int el_1, el_2;
while(i<nums1.size() and j<nums2.size()){
if(nums1[i] < nums2[j]){
if(count == idx1) el_1 = nums1[i];
if(count == idx2) el_2 = nums1[i];
count++;
i++;
}
else{
if(count == idx1) el_1 = nums2[j];
if(count == idx2) el_2 = nums2[j];
count++;
j++;
}
}
while(i<nums1.size()){
if(count == idx1) el_1 = nums1[i];
if(count == idx2) el_2 = nums1[i];
count++;
i++;
}
while(j<nums2.size()){
if(count == idx1) el_1 = nums2[j];
if(count == idx2) el_2 = nums2[j];
count++;
j++;
}
cout<<el_1<<" "<<el_2<<endl;
if((m+n) % 2 == 0)
return (el_1 + (double)el_2) / 2.0;
return el_1;
}
};
Approach 4:
Optimal-> Binary Search
log(min(n,m))
Basically
1 2 3 4 5 6 7 8 9
Some elements come from arr1, other from arr2
symmetry Choose half elements
Now Try to take some elements from arr1 and some from arr2, for this half
arr1 = 1 3 4 7 10 12
arr2 = 2 3 6 15
To choose 5 elements for left half
1 3 4l1 | r1 7 10 12
2 3l2 | r2 6 15
Compare l1 with r2, l2 with r1
To shrink or expand the BS on taking more or less from the array
,
To find for odd
m+n+1/2 used
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if(m>n)
return findMedianSortedArrays(nums2,nums1);
int low=0, high=m;
int left = (m+n+1)/2;
while(low<=high){
int mid1 = low+(high-low)/2;
int mid2 = left-mid1;
int l1=INT_MIN, l2=INT_MIN;
int r1=INT_MAX, r2=INT_MAX;
if(mid1 < m) r1=nums1[mid1];
if(mid2 < n) r2=nums2[mid2];
if(mid1-1 >=0) l1=nums1[mid1-1];
if(mid2-1 >=0) l2=nums2[mid2-1];
if(l1<=r2 and l2<=r1){
if( (m+n) % 2 == 1)
return max(l1,l2);
return (max(l1,l2) + min(r1,r2)) / 2.0;
}
else if(l1>r2)
high = mid1-1;
else
low = mid1+1;
}
return 0;
}
};
Similar Problems
Last updated