Median of Two Sorted Arrays LeetCode problem Solution

Median of Two Sorted Arrays LeetCode problem Solution

by

In this post, we are going to Median of Two Sorted Arrays LeetCode problem which is related to Array, Binary Search, Divide and Conquer. Let’s have a look at the problem statement first and then try to solve the problem.

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

Median of Two Sorted Arrays Leetcode Problem Solutions

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in JavaScript

var findMedianSortedArrays = function(nums1, nums2) {
    let n1 = nums1.length;
    let n2 = nums2.length;
   
    // If nums1 is larger than nums2, swap them to ensure n1 is smaller than n2.
    if (n1 > n2) {
        return findMedianSortedArrays(nums2, nums1);
    }
   
    let l = 0;
    let r = n1;
    while (l <= r) {
        let mid1 = Math.floor((l + r) / 2);
        let mid2 = Math.floor((n1 + n2 + 1) / 2 - mid1);
       
        let maxLeft1 = (mid1 == 0) ? Number.MIN_SAFE_INTEGER : nums1[mid1-1];
        let minRight1 = (mid1 == n1) ? Number.MAX_SAFE_INTEGER : nums1[mid1];
       
        let maxLeft2 = (mid2 == 0) ? Number.MIN_SAFE_INTEGER : nums2[mid2-1];
        let minRight2 = (mid2 == n2) ? Number.MAX_SAFE_INTEGER : nums2[mid2];
       
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((n1 + n2) % 2 == 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            r = mid1 - 1;
        } else {
            l = mid1 + 1;
        }
    }
   
    return -1;
};

Problem Solution in C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
       
        // If nums1 is larger than nums2, swap them to ensure n1 is smaller than n2.
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }
       
        int l = 0;
        int r = n1;
        while (l <= r) {
            int mid1 = (l + r) / 2;
            int mid2 = (n1 + n2 + 1) / 2 - mid1;
           
            int maxLeft1 = (mid1 == 0) ? INT_MIN : nums1[mid1-1];
            int minRight1 = (mid1 == n1) ? INT_MAX : nums1[mid1];
           
            int maxLeft2 = (mid2 == 0) ? INT_MIN : nums2[mid2-1];
            int minRight2 = (mid2 == n2) ? INT_MAX : nums2[mid2];
           
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((n1 + n2) % 2 == 0) {
                    return (double)(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2;
                } else {
                    return (double)max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                r = mid1 - 1;
            } else {
                l = mid1 + 1;
            }
        }
       
        return -1;
    }
};

Problem Solution in Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        n1 = len(nums1)
        n2 = len(nums2)


        # If nums1 is larger than nums2, swap them to ensure n1 is smaller than n2.
        if n1 > n2:
            return self.findMedianSortedArrays(nums2, nums1)


        l = 0
        r = n1
        while l <= r:
            mid1 = (l + r) / 2
            mid2 = (n1 + n2 + 1) / 2 - mid1


            maxLeft1 = nums1[mid1-1] if mid1 != 0 else float('-inf')
            minRight1 = nums1[mid1] if mid1 != n1 else float('inf')


            maxLeft2 = nums2[mid2-1] if mid2 != 0 else float('-inf')
            minRight2 = nums2[mid2] if mid2 != n2 else float('inf')


            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
                if (n1 + n2) % 2 == 0:
                    return float(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
                else:
                    return float(max(maxLeft1, maxLeft2))
            elif maxLeft1 > minRight2:
                r = mid1 - 1
            else:
                l = mid1 + 1


        return -1

Leave a Comment