In this post, we are going to solve the Median of Two Sorted Arrays Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
Problem
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
Now, let’s see the code of Median of Two Sorted Arrays Leetcode Solution.
Median of Two Sorted Arrays Leetcode Solution in Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2, nums1)
l = 0
r = n1
while l <= r:
partition1 = (l + r) // 2
partition2 = (n1 + n2 + 1) // 2 - partition1
maxLeft1 = -2**31 if partition1 == 0 else nums1[partition1 - 1]
maxLeft2 = -2**31 if partition2 == 0 else nums2[partition2 - 1]
minRight1 = 2**31 - 1 if partition1 == n1 else nums1[partition1]
minRight2 = 2**31 - 1 if partition2 == n2 else nums2[partition2]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5 if (n1 + n2) % 2 == 0 else max(maxLeft1, maxLeft2)
elif maxLeft1 > minRight2:
r = partition1 - 1
else:
l = partition1 + 1
Median of Two Sorted Arrays Leetcode Solution in CPP
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int n1 = nums1.size();
const int n2 = nums2.size();
if (n1 > n2)
return findMedianSortedArrays(nums2, nums1);
int l = 0;
int r = n1;
while (l <= r) {
const int partition1 = (l + r) / 2;
const int partition2 = (n1 + n2 + 1) / 2 - partition1;
const int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
const int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
const int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
const int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
return (n1 + n2) % 2 == 0
? (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5
: max(maxLeft1, maxLeft2);
else if (maxLeft1 > minRight2)
r = partition1 - 1;
else
l = partition1 + 1;
}
throw;
}
};
Median of Two Sorted Arrays Leetcode Solution in Java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
final int n1 = nums1.length;
final int n2 = nums2.length;
if (n1 > n2)
return findMedianSortedArrays(nums2, nums1);
int l = 0;
int r = n1;
while (l <= r) {
final int partition1 = (l + r) / 2;
final int partition2 = (n1 + n2 + 1) / 2 - partition1;
final int maxLeft1 = partition1 == 0 ? Integer.MIN_VALUE : nums1[partition1 - 1];
final int maxLeft2 = partition2 == 0 ? Integer.MIN_VALUE : nums2[partition2 - 1];
final int minRight1 = partition1 == n1 ? Integer.MAX_VALUE : nums1[partition1];
final int minRight2 = partition2 == n2 ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
return (n1 + n2) % 2 == 0
? (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) * 0.5
: Math.max(maxLeft1, maxLeft2);
else if (maxLeft1 > minRight2)
r = partition1 - 1;
else
l = partition1 + 1;
}
throw new IllegalArgumentException();
}
}
Note: This problem Median of Two Sorted Arrays is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
