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≤r1
l1≤r2
l2≤r2
l2≤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)