Median of Two Sorted Arrays | Leetcode Problem #4

In this question, given two sorted arrays nums1 and nums2 of size m and n respectively, you have to return the median of two sorted arrays

Goal: The overall run time complexity should be O(log(m+n))

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
 //merged array = [1,2,3] and median is 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
 //merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5

Input: nums1 = [10, 20, 30, 40, 50], nums2 = [5, 15, 25, 35, 45]
Output: 27.50000 //merged array = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] and median is (25 + 30) / 2 = 27.5 

Input: nums1 = [1, 2, 3, 4, 5, 6], nums2 = [10, 20, 30, 40, 50]
Output: 6.00000 //merged array = [1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50] and median is 6

Naive Solution to Find Median of Two Sorted Arrays

In this solution, we create a vector and then insert all the elements of nums1 and nums2 in it. Then we’ll sort the vector and check if the size of the vector is odd or even. If it is odd then we’ll return the middle element of the vector and if it is even then we’ll return the average value of the middle elements. Below we have shown the C++ program to find the median of two sorted arrays.

class Solution {
public:
    //program to find median of two sorted arrays
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size(), i, m = nums1.size();
        vector<int> sol;//creating a vector to merge all the elements of nums1 and nums2
        
        for(i = 0;i<m;i++)
            sol.push_back(nums1[i]);//adding all the elements of nums1 to sol
        for(i=0; i<n; i++)
            sol.push_back(nums2[i]);//adding all the elements of nums2 to sol
        sort(sol.begin(), sol.end());//sorting the merged array
        if((m+n)%2==1)//checking if the size of the vector is odd
            return sol[(m+n+1)/2 - 1];
        else
            return (sol[(m+n)/2]+sol[(m+n)/2 -1])/2.0;//if the size of the vector is not odd then this statement is executed
        
    }
};

Time Complexity : O(m+n)*log(m+n)
Space Complexity: O(n+m)

Although this is the simplest approach one can think of, but it does not fulfil the time complexity criteria and that’s what makes this question a bit hard to solve.

Median of Two Sorted Arrays Binary Search Solution

This is the most efficient method to find the median of two sorted arrays. Basic idea is to calculate the median of both the arrays and discard one half of each of the arrays.

Algorithm

1. Since the algorithm is iterating over the smaller array, the function is called again in order to ensure that nums1 is the smaller array.
2. Now we have to do the partition of both the arrays. Here we calculate the maximum elements (max1 and max2) of respective arrays of the left side and minimum elements (min1 and min2) of respective arrays of the right side. We have to make sure that the maximum element of the left side of the arrays should be less than equal to the minimum element of the right side.
3. Once we find the right partition, we have to calculate the median. In case n+m is odd then we can say that median = max(max1, max2) otherwise median = average of max(max1, max2) and min(min1, min2).

class Solution {
public:
    //median of two sorted arrays binary search
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        //this statement is to ensure that we apply binary search to the smallest array
        if(n < m){
            return findMedianSortedArrays(nums2, nums1); 
        }
        int low = 0, high = m;
        while(low <= high){
            int i1 = (low+high)/2;
            int i2 = (m+n+1)/2-i1;
            
            int max1 = (i1 == 0)? INT_MIN: nums1[i1-1];//taking care of the corner cases
            int min1 = (i1 == m)? INT_MAX: nums1[i1];
            
            int max2 = (i2 == 0)? INT_MIN: nums2[i2-1];
            int min2 = (i2 == n)? INT_MAX: nums2[i2];
            
            if(max1 <= min2 and max2 <= min1){//applying binary search algorithm
                if((m+n)%2 == 1)
                    return (double)max(max1, max2);
                else
                    return ((double)max(max1, max2)+min(min1, min2))/2;
            }
            else if(max1 > min2)
                high = i1-1;
            else
                low = i1+1;
        }
        return 0.0;
    }
};

Time Complexity: O(log(min(m,n)))
Space Complexity: O(1)

Dry Run

Input: nums1 = [10, 20, 30], nums2 = [5, 15, 25, 35, 45]

Iteration 1
low=0, high=2
i1 = 1, i2 = (5+3+1)/2-1 = 3
max1 = 10, min1 = 20, max2 = 25, min2 = 35
Since max(max1, max2) = 25 > min(min1, min2)=20

Iteration 2
low=2, high2
i1 = 2, i2 = (5+3+1)/2-2 = 2
max1 = 20, min1 = 30, max2 = 15, min2 = 25
Since min(min1, min2)>max(max1, max2), we calculate median = 25+20 = 22.5

Hope you found this article interesting and for more interesting topics you can refer to Find Peak Element in Array | Leetcode Problem #162 and Window Sliding Technique – An Efficient Technique