Last updated on January 12th, 2025 at 04:00 am
Here, We see Median of Two Sorted Arrays LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
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
1. 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.
2. Coding Pattern Used in Solution
- Java Code and Python Code:
- Pattern Used: Two Pointers
- The Java and Python implementations use the Two Pointers technique. Two pointers traverse the two sorted arrays simultaneously. The pointers compare elements from both arrays and move forward to merge the arrays up to the middle point, which is sufficient to find the median.
- C++ Code and JavaScript Code:
- Pattern Used: Modified Binary Search
- The C++ and JavaScript implementations use a Modified Binary Search approach. The smaller array is partitioned using binary search, and the partitioning is adjusted to ensure that the left and right halves of the combined arrays are balanced. This allows the median to be calculated in logarithmic time.
3. Code Implementation in Different Languages
3.1 Median of Two Sorted Arrays 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;
}
};
3.2 Median of Two Sorted Arrays 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;
}
}
3.3 Median of Two Sorted Arrays 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.4 Median of Two Sorted Arrays 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) / 2
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(log(min(m, n))) | O(1) |
| Java | O(m + n) | O(1) |
| JavaScript | O(log(min(m, n))) | O(1) |
| Python | O(m + n) | O(1) |
- The Two Pointers approach (Java and Python) is simpler but less efficient for large arrays.
- The Modified Binary Search approach (C++ and JavaScript) is more efficient, especially when the arrays are large and one is significantly smaller than the other.