Median of Two Sorted Arrays LeetCode Solution

Here, We see Median of Two Sorted Arrays problem Solution. This Leetcode problem done in many programming language like C++, Java, JavaScript, Python etc. with different approach.

Median of Two Sorted Arrays LeetCode Solution

Median of Two Sorted Arrays LeetCode Solution

Problem Statement ->

Given two sorted arrays nums1 and nums2 of size and 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.

C++ Solution ->

class Solution { public: double mediann(vector<int>&a,vector<int>&b){ int m=a.size(); int n=b.size(); if(m>n) return mediann(b,a); int l=0,r=m; while(l<=r){ int partx=l+(r-l)/2; int party=(m+n+1)/2-partx; int maxlx=(partx==0)?INT_MIN:a[partx-1]; int minrx=(partx==m)?INT_MAX:a[partx]; int maxly=(party==0)?INT_MIN:b[party-1]; int minry=(party==n)?INT_MAX:b[party]; if(maxlx<=minry&&maxly<=minrx){ if((m+n)%2==0) return (double)(max(maxlx,maxly)+min(minrx,minry))/2; else return (double)(max(maxlx,maxly)); }else if(maxlx>minry) r=partx-1; else l=partx+1; } return -1.0; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { double ans; ans=mediann(nums1,nums2); return ans; } };
Code language: C++ (cpp)

Java Solution ->

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int index1 = 0; int index2 = 0; int med1 = 0; int med2 = 0; for (int i=0; i<=(nums1.length+nums2.length)/2; i++) { med1 = med2; if (index1 == nums1.length) { med2 = nums2[index2]; index2++; } else if (index2 == nums2.length) { med2 = nums1[index1]; index1++; } else if (nums1[index1] < nums2[index2] ) { med2 = nums1[index1]; index1++; } else { med2 = nums2[index2]; index2++; } } // the median is the average of two numbers if ((nums1.length+nums2.length)%2 == 0) { return (float)(med1+med2)/2; } return med2; } }
Code language: Java (java)

JavaScript Solution ->

var findMedianSortedArrays = function(nums1, nums2) { if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1) let x = nums1.length let y = nums2.length let low = 0, high = x while(low <= high) { const partitionX = (high + low) >> 1 const partitionY = ((x + y + 1) >> 1) - partitionX const maxX = partitionX == 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1] const maxY = partitionY == 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1] const minX = partitionX == nums1.length ? Number.POSITIVE_INFINITY : nums1[partitionX] const minY = partitionY == nums2.length ? Number.POSITIVE_INFINITY : nums2[partitionY ] if(maxX <= minY && maxY <= minX) { const lowMax = Math.max(maxX, maxY) if( (x + y) % 2 == 1) return lowMax return (lowMax + Math.min(minX, minY)) / 2 } else if(maxX < minY) { low = partitionX + 1 } else high = partitionX - 1 } };
Code language: JavaScript (javascript)

Python Solution ->

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: m, n = len(nums1), len(nums2) mid = (m + n) // 2 + 1 prev2 = prev1 = None i = j = 0 for _ in range(mid): prev2 = prev1 if j == n or (i != m and nums1[i] <= nums2[j]): prev1 = nums1[i] i += 1 else: prev1 = nums2[j] j += 1 return prev1 if (m + n) % 2 else (prev1 + prev2) / 2
Code language: Python (python)

Median of Two Sorted Arrays, Leetcode Median of Two Sorted Arrays, Median of Two Sorted Arrays python solution, Median of Two Sorted Arrays java solution, Median of Two Sorted Arrays JavaScript solution, Median of Two Sorted Arrays C++ solution

Leave a Comment

Your email address will not be published.