Last updated on October 10th, 2024 at 12:46 am
Here, We see Median of Two Sorted Arrays LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
List of all LeetCode Solution
Topics
Array, Binary Search, Divide and Conquer
Companies
Adobe, Apple, Dropbox, Google, Microsoft, Yahoo, Zenefits
Level of Questions
Hard
Median of Two Sorted Arrays LeetCode Solution
Table of Contents
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.
1. Median of Two Sorted Arrays Leetcode Solution C++
class Solution {
public:
double mediann(vector<int>&a,vector<int>&b){
int m=a.size();
int n=b.size();
if(m>n)
return mediann(b,a);
int l=0,r=m;
while(l<=r){
int partx=l+(r-l)/2;
int party=(m+n+1)/2-partx;
int maxlx=(partx==0)?INT_MIN:a[partx-1];
int minrx=(partx==m)?INT_MAX:a[partx];
int maxly=(party==0)?INT_MIN:b[party-1];
int minry=(party==n)?INT_MAX:b[party];
if(maxlx<=minry&&maxly<=minrx){
if((m+n)%2==0)
return (double)(max(maxlx,maxly)+min(minrx,minry))/2;
else
return (double)(max(maxlx,maxly));
}else if(maxlx>minry)
r=partx-1;
else
l=partx+1;
}
return -1.0;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double ans;
ans=mediann(nums1,nums2);
return ans;
}
};1.1 Explanation
- The function mediann is called by findMedianSortedArrays with nums1 and nums2.
- The smaller array is always passed as the first argument to mediann to ensure m <= n.
- The binary search is performed on the smaller array to find the correct partition.
- maxlx, minrx, maxly, and minry represent the maximum and minimum values on the left and right of the partitions in both arrays.
- If the partitions are correct (i.e., maxlx <= minry and maxly <= minrx), the median is calculated.
- If the combined length of both arrays is even, the median is the average of the two middle elements. If odd, it is the middle element.
- Adjust the binary search range based on the comparison between maxlx and minry.
1.2 Time Complexity
O(log(min(m, n))), where m and n are the lengths of the two arrays.
1.3 Space Complexity
O(1)
2. Median of Two Sorted Arrays Leetcode Solution Java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int index1 = 0;
int index2 = 0;
int med1 = 0;
int med2 = 0;
for (int i=0; i<=(nums1.length+nums2.length)/2; i++) {
med1 = med2;
if (index1 == nums1.length) {
med2 = nums2[index2];
index2++;
} else if (index2 == nums2.length) {
med2 = nums1[index1];
index1++;
} else if (nums1[index1] < nums2[index2] ) {
med2 = nums1[index1];
index1++;
} else {
med2 = nums2[index2];
index2++;
}
}
// the median is the average of two numbers
if ((nums1.length+nums2.length)%2 == 0) {
return (float)(med1+med2)/2;
}
return med2;
}
}2.1 Explanation
- Initialize index1 and index2 to traverse nums1 and nums2.
- Traverse until the middle point of the combined arrays.
- Update med1 and med2 to store the last two values considered.
- Compare the current elements of nums1 and nums2 and update indices accordingly.
- If the total length is even, return the average of med1 and med2. If odd, return med2.
2.2 Time Complexity
O(m + n), where m and n are the lengths of the two arrays.
2.3 Space Complexity
O(1)
3. Median of Two Sorted Arrays Leetcode Solution JavaScript
var findMedianSortedArrays = function(nums1, nums2) {
if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1)
let x = nums1.length
let y = nums2.length
let low = 0, high = x
while(low <= high) {
const partitionX = (high + low) >> 1
const partitionY = ((x + y + 1) >> 1) - partitionX
const maxX = partitionX == 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1]
const maxY = partitionY == 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1]
const minX = partitionX == nums1.length ? Number.POSITIVE_INFINITY : nums1[partitionX]
const minY = partitionY == nums2.length ? Number.POSITIVE_INFINITY : nums2[partitionY ]
if(maxX <= minY && maxY <= minX) {
const lowMax = Math.max(maxX, maxY)
if( (x + y) % 2 == 1)
return lowMax
return (lowMax + Math.min(minX, minY)) / 2
} else if(maxX < minY) {
low = partitionX + 1
} else
high = partitionX - 1
}
};3.1 Explanation
- Swap arrays if nums1 is longer than nums2 to ensure binary search on the smaller array.
- Perform binary search on nums1 to find the correct partition.
- Calculate partitionX and partitionY based on the middle index.
- Determine maxX, maxY, minX, and minY.
- Check if partitions are correct. If yes, calculate the median.
- If not, adjust the binary search range based on comparisons.
3.2 Time Complexity
O(log(min(m, n)))
3.3 Space Complexity
O(1)
4. Median of Two Sorted Arrays Leetcode Solution Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
mid = (m + n) // 2 + 1
prev2 = prev1 = None
i = j = 0
for _ in range(mid):
prev2 = prev1
if j == n or (i != m and nums1[i] <= nums2[j]):
prev1 = nums1[i]
i += 1
else:
prev1 = nums2[j]
j += 1
return prev1 if (m + n) % 2 else (prev1 + prev2) / 24.1 Explanation
- Determine the lengths of nums1 and nums2.
- Calculate the middle index mid.
- Initialize prev1 and prev2 to store the last two values considered.
- Traverse until the middle point of the combined arrays.
- Compare elements from nums1 and nums2, and update prev1 and prev2.
- If the total length is even, return the average of prev1 and prev2. If odd, return prev1.
4.2 Time Complexity
O(m + n)
4.3 Space Complexity
O(1)