Median of Two Sorted Arrays Problem

Difficulty – Hard

Median of Two Sorted Arrays: 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.

Median of Two Sorted Arrays Problem Solution

Problem Solution In Python

class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        med1 = med2 = i = j = 0
        n = len(A) + len(B)
        
        while (i + j) <= n / 2:
            if i < len(A) and j < len(B):
                med2 = med1
                if A[i] < B[j]:
                    med1 = A[i]
                    i += 1
                else:
                    med1 = B[j]
                    j += 1
            elif i < len(A):
                med2 = med1
                med1 = A[i]
                i += 1
            elif j < len(B):
                med2 = med1
                med1 = B[j]
                j += 1

        if n % 2 == 0:
            return (med1 + med2) / 2.0
        else:
            return med1

Problem Solution In Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<nums1.length;i++)
        {
            list.add(nums1[i]);
        }
        for(int i=0;i<nums2.length;i++)
        {
            list.add(nums2[i]);
        }
        Collections.sort(list);
        int size=list.size();

        if (size % 2 == 1)   return (double) list.get(size/2);
        
          return (double) (list.get((size/2)-1) + list.get(size/2) )/2;
        
    }
}

Problem Solution In C++

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        nums1.insert(nums1.begin(), nums2.begin(), nums2.end());
        sort(nums1.begin(), nums1.end());
        
        int median = nums1.size()/2;
        if(nums1.size()%2 == 1) 
        {
            return nums1[median];
        }
        else
        {
            return (double)(nums1[median]+nums1[median-1])/2;
        }
    }

Problem Solution In C

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int len = nums1Size + nums2Size;
    int merged[len];
    int i = 0, j = 0, idx = 0;
    while (i < nums1Size || j < nums2Size) {
        if (i < nums1Size && j < nums2Size) {
            if (nums1[i] < nums2[j]) {
                merged[idx++] = nums1[i++];
            } else {
                merged[idx++] = nums2[j++];
            }
        } else if (i < nums1Size) {
            merged[idx++] = nums1[i++];
        } else {
            merged[idx++] = nums2[j++];
        }
    }
    
    if (len % 2 == 0) {
        return ((merged[len/2 - 1] + merged[len/2]) / 2.0);
    } else {
        return merged[len/2];
    }
}

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment