Placement

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;
}

Java Solution :

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;

};
Facebook
Twitter
LinkedIn

2 thoughts on “Leet Code : Median of two sorted array -CPP || java || Python || Java Script”

  1. So, your algorithm is first merging both vectors in sorted order and finding median on final vector.
    I will take O(n + m) of total time and space complexity. But according to question you must do it in O(log(n + m)) of overall time complexity.

    Can your do it ? and is it even possible to do it?

    Reply
    • 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;
      }

      Reply

Leave a Comment