Median of Two Sorted Arrays (in Python)

Problem

There are two sorted arrays num1 and num2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

You may assume nums1 and nums2 cannot be both empty.

Solution

Approach 1 : Sort and find

My first approach was just put them together and find median. It costs same time with the second approach on Leetcode. But it will waste a lot of time to sort all of them even it was already sorted.

def findMedianSortedArrays(self, nums1, nums2):
 
    newArr = nums1 + nums2
    newArr.sort()
 
    x = len(newArr) // 2
    y = len(newArr) % 2
    ans = 0
 
    if(y == 0) :
        ans = (newArr[x]+newArr[x-1])/2
    else :
        ans = newArr[x]
 
    return ans

Complexity Analysis

•Time complexity : O((m+n)log(m+n)). Because python uses Timsort. 

•Space complexity : O(m+n).

---

Approach 2 : Recursive Approach

To solve this problem, we need to understand "What is the use of median". In statistics, the median is used for :

Dividing a set into two equal length subsets, that one subset is always greater than the other.

I highly recommend that you just watch the video below.

https://www.youtube.com/watch?v=LPFhl65R7ww 

def findMedianSortedArrays(self, nums1, nums2):
 
    m, n = len(nums1), len(nums2)
        
    if m > n : 
        nums1, nums2 = nums2, nums1
        m, n = n, m
        
    imin, imax = 0, m
    half_len = (m+n+1) // 2
 
    while imin <= imax :
 
       i = (imin + imax) // 2
       j = half_len - i
 
       # 파티션이 너무 오른쪽으로 치우쳐짐. 왼쪽으로 움직여야함.
       if i > 0 and nums1[i-1] > nums2[j] :
            imax -= 1
       # 파티션이 너무 왼쪽으로 치우쳐짐. 오른쪽으로 움직여야함.
       elif i < m and nums1[i] < nums2[j-1] : 
            imin += 1
       else :
 
             # 왼쪽 집합에서 가장 큰 요소를 찾음.
             if i == 0 :
                  max_of_left = nums2[j-1]
             elif j == 0 :
                  max_of_left = nums1[i-1]
             else :
                  max_of_left = max(nums1[i-1], nums2[j-1])
 
             if (m+n) % 2 == 1 :
                  return max_of_left
 
             # 오른쪽 집합에서 가장 작은 요소를 찾음.
             if i == m :
                  min_of_right = nums2[j]
             elif j == n :
                  min_of_right = nums1[i]
             else :
                  min_of_right = min(nums1[i], nums2[j])
                      
             return (max_of_left + min_of_right) / 2 

    return ans

Complexity Analysis

•Time complexity : O(log(min(m,n)))

At first, the searching range is [0, m]. And the length of this searching range will be reduced by half after each loop. So, we only need log(m) loops. Since we do constant operations in each loop, so the time complexity is O(log(m)). Since m≤n, so the time complexity is O(log(min(m,n))).

•Space complexity : O(1). We only need constant memory to store 9 local variables, so the space complexity is O(1).

Source: https://leetcode.com/problems/median-of-two-sorted-arrays