4. Median of Two Sorted Arrays
Median of Two Sorted Arrays
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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Explanation
- Let us take the first example and find the median of two sorted arrays.
- The first array (a1) is [ 1, 12, 15, 26, 38 ] The second array (a2) is [ 2, 13, 17, 30, 45 ]
- After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]
- The average of the two middle elements is: (15 + 17)/2 i.e. 16.
Note:
If the size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.
Approach 1) Simply Count While Merging
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array. We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays. Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n-1 th element and nth element as the size of the merged array is even.
Algorithm
The pseudo-code for the algorithm can be:
- Initialize a counter variable.
- Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
- Finally, return the average of the element present at the index n-1 and n in the array.
Let`s Code IT!
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let mergedArray = [];
let left = 0, right = 0, counter = 0;
while(nums1.length > left && nums2.length > right){
if(nums1[left] > nums2[right]){
mergedArray.push(nums2[right]);
right++;
}else if(nums1[left] <= nums2[right]){
mergedArray.push(nums1[left]);
left++;
}
}
for(let i=left;i<nums1.length;i++){
mergedArray.push(nums1[i]);
}
for(let j=right;j<nums2.length;j++){
mergedArray.push(nums2[j]);
}
if(mergedArray.length % 2 !== 0){
let index = Math.floor(mergedArray.length / 2);
return mergedArray[index];
}else{
let index = Math.floor((mergedArray.length - 1) / 2);
return (mergedArray[index] + mergedArray[index+1]) / 2;
}
};Complexity AnalysisIn this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.
Time ComplexityAs we are traversing only the first n elements of the arrays, the time complexity is O(n).
Space ComplexityWe are not using any extra space rather than a count variable. So, space complexity is O(1).
Approach 2) By Comparing the Medians of Two ArraysIn the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.
AlgorithmThe pseudo-code for the algorithm can be:- First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
- If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
- If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- - from the first element of a1 to the firstMedian.
- - or from the secondMedian to the last element of a2.
- If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- - from the firstMedian to the first element of a1.
- - or from the first element of a2 to the secondMedian.
- Repeat the process until the size of the sub-arrays becomes 2.
- If the size of the sub arrays becomes 2, then median is:
- Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
Let`s Code IT!/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(a1, a2) {
// a function for finding median of array
let median = function(a, start, end) {
let n = end - start + 1;
// checking if length is even or odd
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
// a recursive function that returns the median of the array
let findMedian = function(a1, a2, start_a1,
start_a2, end_a1, end_a2) {
// base case
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
// median of the first array
let m1 = median(a1, start_a1, end_a1);
// median of the second array
let m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
// if the median of the first array is smaller then recursively call the function
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
return findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1)
};
Complexity AnalysisIn this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.
Time ComplexitySo, the time complexity is O(log n).
Space ComplexityWe are not using any extra space. So, space complexity is O(1).
Approach 3: By Taking Union w/o Extra SpaceIn the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.
AlgorithmThe pseudo-code for the algorithm can be:- Find the union of both the input arrays.
- Sort both the arrays respectively.
- Find the median by the formula:
- Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
Let`s Code IT!
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const union = [];
union.push(...nums1, ...nums2);
const sortedUnion = union.sort((a,b) => a - b);
const midcount = sortedUnion.length/2;
return sortedUnion.length % 2 === 0 ? (sortedUnion[midcount-1] + sortedUnion[midcount])/2 : sortedUnion[Math.ceil(midcount)-1];
};
Complexity AnalysisIn this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation (constant time taking).
Time ComplexitySo, the time complexity is O(n log n).
Space ComplexityWe are not using any extra space. So, space complexity is O(1).
Conclusion
That’s all folks! In this post, we solved LeetCode problem #4. Median of Two Sorted Arrays
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment