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.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
Approach 1:
2 pointer approach
Iterate through the entire array and store the elements to another array in sorted order as a whole. Then find the median based on this newly created array.
class Solution(object): def findMedianSortedArrays(self, nums1, nums2): i,j,total=0,0,[] while(i<len(nums1) or j<len(nums2)): if i>=len(nums1): val1=float('inf') else: val1=nums1[i] if j>=len(nums2): val2=float('inf') else: val2=nums2[j] if val1<val2: total.append(val1) i+=1 else: total.append(val2) j+=1 length=len(total) length=len(total) return([total[length//2],(total[length//2]+total[(length//2)-1])/2][length%2==0])
Time: O(m+n)
Space: O(m+n)
Approach 2:
The space complexity can be reduced to constant time. That is by devoiding the use of the final sorted array. For this we calculate the number of steps we need to move the 2 pointer to reach the middle element . And iterate through both of this array till that many steps or count.
class Solution(object): def findMedianSortedArrays(self, nums1, nums2): pre,curr,ptr1,ptr2=0,0,0,0 cnt=(len(nums1)+len(nums2))//2 + 1 ptr1,ptr2=0,0 while(cnt): if ptr1==len(nums1): val1=float('inf') else: val1=nums1[ptr1] if ptr2==len(nums2): val2=float('inf') else: val2=nums2[ptr2] if val1<val2: prev=curr curr=val1 ptr1+=1 else: prev=curr curr=val2 ptr2+=1 cnt-=1 return([curr,(prev+curr)/2][(len(nums1)+len(nums2))%2==0])
Time: O(m+n)
Space: O(1)
Approach 3:
Binary Search
Since the array s are sorted , we can take advantage of binary search . Essentially what we do here is , find the point of partition of both array such that we get 2 cluster partitioned around median value. It is obtained by findingg partition point named as cut1 and cut2 .
The condition for getting to know that we have reached partition point around the median value is , by checking that all the values in cluster 1 is less than cluster 2 .
which is by checking :
l1≤r1l1≤r2l2≤r2l2≤r1
l1,l2 are the last elements of nums1 and num2 respectively, in cluster 1
and r1 and r2 are the first elements in nums1 and nums2 respectively , in cluster 2
condition 1 and 3 needn’t be checked as the arrays are sorted by itself. Only condition 2 and 4 matters.
The median value may be lying in the cluster 2 , when total number of elements are odd and when it is even , one of the value contributing to median will be in cluster 1 and other in cluster 2, so we take average of them .
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
if len(nums2)<len(nums1):
nums1,nums2=nums2,nums1
total=len(nums1)+len(nums2)
half=total//2
l,h,=0,len(nums1)-1
while(True):
mid=(l+h)//2
cut1=mid
cut2=half-cut1-2
l1 = -1*float('inf') if cut1<0 else nums1[cut1]
l2 = -1*float('inf') if cut2<0 else nums2[cut2]
r1 = float('inf') if cut1>=len(nums1)-1 else nums1[cut1+1]
r2 = float('inf') if cut2>=len(nums2)-1 else nums2[cut2+1]
if l1<=r2 and l2<=r1:
return([min(r1,r2),(max(l1,l2)+min(r1,r2))/2][total%2==0])
elif l1>r2:
h=mid-1
else:
l=mid+1
Time: O (log(m+n))
Space: O(1)