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