4. Median of Two Sorted Arrays

Problem Statement

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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

Intuition

Links

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Video Links

https://www.youtube.com/watch?v=C2rRzz-JDk8&ab_channel=takeUforward

Approach 1:

Brute:
NlogN time and 1 Space

Directly Inserted one array in other and used sort

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        nums1.insert(nums1.end(), nums2.begin(), nums2.end());
        sort(nums1.begin(), nums1.end());

        int n = nums1.size();
        if(n == 0)  return 0;
        int idx = n/2;
        if(n%2 == 0)
            return (nums1[idx]+nums1[idx-1])/2.0;
        
        return nums1[idx];
    }
};

Approach 2:

Merge Algorithm
m+n time and m+n space

Merged two sorted using pointers in other array

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> arr;
        int i=0, j=0;

        while(i<nums1.size() and j<nums2.size()){
            if(nums1[i] < nums2[j])
                arr.push_back(nums1[i++]);
            else
                arr.push_back(nums2[j++]);
        }

        while(i<nums1.size())
            arr.push_back(nums1[i++]);

        while(j<nums2.size())
            arr.push_back(nums2[j++]);

        int index = arr.size()/2;
        if(arr.size() % 2 == 0)
            return (arr[index] + arr[index-1]) / 2.0;

        return arr[index];
    }
};

Approach 3:

Merge Algorithm optimised
m+n time and 1 space

Maintained variables to keep track of index

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int i=0, j=0;
        int count = 0;
        int idx1 = (m+n)/2;
        int idx2 = idx1-1;
        int el_1, el_2;

        while(i<nums1.size() and j<nums2.size()){
            if(nums1[i] < nums2[j]){
                if(count == idx1)   el_1 = nums1[i];
                if(count == idx2)   el_2 = nums1[i];
                count++;
                i++;
            }
            else{
                if(count == idx1)   el_1 = nums2[j];
                if(count == idx2)   el_2 = nums2[j];
                count++;
                j++;
            }
        }

        while(i<nums1.size()){
            if(count == idx1)   el_1 = nums1[i];
            if(count == idx2)   el_2 = nums1[i];
            count++;
            i++;
        }

        while(j<nums2.size()){
            if(count == idx1)   el_1 = nums2[j];
            if(count == idx2)   el_2 = nums2[j];
            count++;
            j++;
        }
        cout<<el_1<<" "<<el_2<<endl;
        if((m+n) % 2 == 0)
            return (el_1 + (double)el_2) / 2.0;

        return el_1;
    }
};

Approach 4:

Optimal-> Binary Search
log(min(n,m))

Basically
1 2 3 4 5 6 7 8 9
Some elements come from arr1, other from arr2

symmetry Choose half elements

Now Try to take some elements from arr1 and some from arr2, for this half

arr1 = 1 3 4 7 10 12
arr2 = 2 3 6 15

To choose 5 elements for left half

1 3 4l1 | r1 7 10 12
2 3l2   | r2 6 15

Compare  l1 with r2, l2 with r1
To shrink or expand the BS on taking more or less from the array

,

To find for odd
m+n+1/2 used

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m>n) 
            return findMedianSortedArrays(nums2,nums1);

        int low=0, high=m;
        int left = (m+n+1)/2;
        while(low<=high){
            int mid1 = low+(high-low)/2;
            int mid2 = left-mid1;

            int l1=INT_MIN, l2=INT_MIN;
            int r1=INT_MAX, r2=INT_MAX;

            if(mid1 < m)    r1=nums1[mid1];
            if(mid2 < n)    r2=nums2[mid2];
            if(mid1-1 >=0)  l1=nums1[mid1-1];
            if(mid2-1 >=0)  l2=nums2[mid2-1];

            if(l1<=r2 and l2<=r1){
                if( (m+n) % 2 == 1)
                    return max(l1,l2);

                return (max(l1,l2) + min(r1,r2)) / 2.0;
            } 
            else if(l1>r2)
                high = mid1-1;
            else
                low = mid1+1;
        }

        return 0;
    }
};