Home » leet code » Leet Code : Median of two sorted array -CPP || java || Python || Java Script

# Leet Code : Median of two sorted array -CPP || java || Python || Java Script

Provide the median of the two sorted arrays given two sorted arrays of sizes m and n, respectively.

The entire complexity of the run time should be O(log (m+n)).

Eg 1:

Numbers1 = [1,3], Numbers2 = [2]

Result: 2.00000

Explanation: the merged array equals [1,2,3], and the median is 2.

Eg 2:

Numbers1 = [1,2], Numbers2 = [3,4]

2.50000 as an output

Explanation: [1,2,3,4] is the merged array, and the median is (2 + 3) / 2 = 2.5.

## solution:

CPP solution

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
vector<int> v;
while(i<nums1.size() && j<nums2.size()){
if(nums1[i] < nums2[j]){
v.push_back(nums1[i]);
i++;
}
else{
v.push_back(nums2[j]);
j++;
}
}
for(i; i<nums1.size(); i++) v.push_back(nums1[i]);
for(j; j<nums2.size(); j++) v.push_back(nums2[j]);

int size = v.size();
int mid = size/2;

if(size%2==0){
return (double(v[mid] + v[mid-1])/2);
}
else return v[mid];
}
};

``````

The O(log(M + N)) CPP Solution ..

``````The O(log(M + N)) Solution..
If You want The Explanation ? i will post article on it.

double findMedianSortedArrays(vector & nums1, vector & nums2) {
int N1 = nums1.size();
int N2 = nums2.size();
if (N1 < N2) return findMedianSortedArrays(nums2, nums1);
// Make sure A2 is the shorter one.
int lo = 0, hi = N2 * 2; while (lo <= hi) { int mid2 = (lo + hi) / 2;
// Try Cut 2
int mid1 = N1 + N2 - mid2;
// Calculate Cut 1 accordingly double
L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];
// Get L1, R1, L2, R2 respectively
double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
if (L1 > R2) lo = mid2 + 1;
// A1’s lower half is too big; need to move C1 left (C2 right)
else if (L2 > R1) hi = mid2– 1;
// A2’s lower half too big; need to move C2 left.
else return (max(L1, L2) + min(R1, R2)) / 2;    // Otherwise, that’s the right cut.
}
return -1;
}``````
``````class Solution
{
public double findMedianSortedArrays(int[] nums1, int[] nums2)
{
int s1=nums1.length;
int s2=nums2.length;
double[] temp=new double[s1+s2];
int i=0,j=0,k=0;
while(i<s1&&j<s2)
{
if(nums1[i]<=nums2[j])
{
temp[k]=nums1[i];
i++;
k++;
}
else
{
temp[k]=nums2[j];
j++;
k++;
}
}
if(i>=s1)
{
for(int t=j;t<s2;t++)
{
temp[k]=nums2[t];
k++;
}
}
if(j>=s2)
{
for(int t=i;t<s1;t++)
{
temp[k]=nums1[t];
k++;
}
}
//just for checking printing temp array
/*for(int t=0;t<k;t++)
System.out.print(temp[t]+" ");*/
double ans=0.0;
if(temp.length%2!=0)
return temp[temp.length/2];
else
return (temp[temp.length/2]+temp[temp.length/2-1])/2;
}
}``````

Java Script /Type Script:

``````function findMedianSortedArrays(nums1: number[], nums2: number[]): number {

const arr = [...nums1, ...nums2];

arr.sort((n1, n2) => n1 - n2);

let half = Math.floor(arr.length / 2);

if (arr.length % 2) {
return arr[half];
}

return (arr[half - 1] + arr[half]) / 2.0;

};``````