Header Ads Widget

Trending

6/recent/ticker-posts

Median of two sorted Arrays

 Problem-: Median of Two Sorted Array

We have Given two arrays arr1 and arr2 and we have to find the median of these two sorted arrays. This is Hard level question that requires an efficient approach to solve. Both Arrays we have are sorted in Ascending order and we have to find the median of two sorted arrays of different sizes.

What is the Median of two sorted Array?

The Median of two sorted arrays is the element at the middle if both the array are merged and sorted in Ascending Order. In the case of an even number of total elements, we take the average of the middle elements of the array.


Example 1:

Input: nums1 = [1,3,6,9], nums2 = [2,4,19]
Output: 4.00000


Basic Approach to Solve Median of two sorted arrays problem 

  • Declare a new array of size (m+n) where m and n are sizes of both the given arrays.
  • Merge Both the arrays in the new array.
  • Sort the new arrays formed in Ascending or Descending Order.
  • If m+n is Odd then the m+n/2th element is the median.
  • If m+n is even then an average of (m+n-1)/2th and m+n/2th element is the Median.

Here is the code for the most basic approach of finding the median of two sorted arrays.
Here is the solution of the median of two sorted arrays in Java 

class Solution {
    public double findMedianSortedArrays(int[] nums1int[] nums2) {
        double res;
        int[] result=new int[nums1.length+nums2.length];
        System.arraycopy(nums1,0,result,0,nums1.length);
        System.arraycopy(nums2,0,result,nums1.length,nums2.length);
            Arrays.sort(result);
        if(result.length%2!=0) res=result[((result.length+1)/2)-1];
else res=(double)(result[((result.length+1)/2)]+result[((result.length-1)/2)])/2;
        return res;
        
    }}


Here Arrays.sort() function sort array in minimum time complexity.

Solution of Median of two sorted arrays in C++


class Solution 
{
public:
double MedianSortedArrays(vector& vect1vector& vect2)
 {
float n = vect1.size();
float m = vect2.size();
vector nums3(m+n);

merge(vect1.begin(),vect1.end(),nums2.begin(),nums2.end(),nums3.begin());

m = m+n-1;
n = 0;
if (nums3.size() < 2)
{

return nums3[0];
}

float f = 0;

while(n <= m)
{

        if(n+1 == m)
        {
            f = (nums3[n] + nums3[m])/2;
            break;
        }
        else if(m == n)
        {
            f = nums3[n];
           break;
        }
        n++;
        m--;
        
    }
    return f;
    
}
};


These solutions are easy to understand and using this algorithm you can solve them inefficient and less complex ways. This problem can be solved in less time complexity by using divide and conqueror or Binary Search Tree.
This solution is the best solution of the Median of two sorted arrays problem for both the type of array either it is of the same size or of different size.
Solve this Problem at Leetcode - Median of two sorted Arrays