Leetcode problem 4 solution using Python - Median of Two Sorted Arrays

Problem

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

Solution 1

This is the simplest solution to this problem using built-in list methods i.e. extend and sort. 

This is not an optimal solution for this problem.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums2.extend(nums1)
        nums2.sort()
        no_items = len(nums2)
        if no_items%2!=0:
            return nums2[no_items//2]
        else:
            return (nums2[no_items//2-1] + nums2[no_items//2])/2

Solution 2

In this solution, we are getting the combined array using 2 pointer methods. This solution is not an optimized solution for this problem. 

class Solution:
  def findMedianSortedArrays(self, nums1, nums2):
    new_list = []
    i = 0; j =0 
    while i<len(nums1) and j<len(nums2):
      if nums1[i] < nums2[j]:
        new_list.append(nums1[i])
        i = i + 1
      else:
        new_list.append(nums2[j])
        j = j + 1
    new_list.extend(nums1[i:])
    new_list.extend(nums2[j:])
    no_items = len(new_list)
    if no_items%2!=0:
        return new_list[no_items//2]
    else:
        return (new_list[no_items//2-1] + new_list[no_items//2])/2

Solution 3

This is the best solution to this problem. This solution uses a binary search algorithm. The overall run time complexity is O(log (m+n)) for this solution. Watch this YouTube video to understand the algorithm - https://youtu.be/NTop3VTjmxk 

class Solution:
  def findMedianSortednums1rrays(self, nums1, nums2):
    total = len(nums1) + len(nums2)
    half = total // 2
            
    if len(nums2) < len(nums1):
        nums1, nums2 = nums2, nums1
            
    l, r = 0, len(nums1) - 1 # l -> left, r-> right
    while True:
        i = (l + r) // 2 # nums1
        j = half - i - 2 # nums2
            
        nums1left = nums1[i] if i >= 0 else float("-infinity")
        nums1right = nums1[i + 1] if (i + 1) < len(nums1) else float("infinity")
        nums2left = nums2[j] if j >= 0 else float("-infinity")
        nums2right = nums2[j + 1] if (j + 1) < len(nums2) else float("infinity")
            
        # partition is correct
        if nums1left <= nums2right and nums2left <= nums1right:
            # odd
            if total % 2:
                return min(nums1right, nums2right)
            # even
            return (max(nums1left, nums2left) + min(nums1right, nums2right)) / 2
        elif nums1left > nums2right:
            r = i - 1
        else:
            l = i + 1