0004. Median of Two Sorted Arrays

Hard | Binary Search | 80 ms (97.98%), 14.5 MB (81.46%)

❓ Problem Statement

Source: LeetCode - Median of Two Sorted Arrays GitHub: Solution / Performance

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)).

✍🏻 Constraints & Example

💡 Ideas

Take the shorter array to be the search space for binary search.

At first, we find the total length of the merged array to understand how many elements are in the left and right parts respectively. size = (total_length + 1) // 2

Next, in each iteration, we take n elements from nums1 and size - n elements from nums2. l, r = 0, len(nums1) n = (l + r) // 2 Then check whether selected elements are valid or not by comparing them with non-selected elements.

If valid, we return the median immediately. If not valid, we modify the search space.

p1 = (l + r) // 2
p2 = size - p1

nums1_left  = float('-inf') if p1 == 0 else nums1[p1 - 1]
nums1_right = float('inf')  if p1 == m else nums1[p1]
nums2_left  = float('-inf') if p2 == 0 else nums2[p2 - 1]
nums2_right = float('inf')  if p2 == n else nums2[p2]

🤖 Python3

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        # ==================================================
        #  Array + Binary Seearch                          =
        # ==================================================
        # time  : O(log(min(m,n)))
        # space : O(1)
        
        if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1)
        
        m, n = len(nums1), len(nums2)
        total = m + n
        size = (total + 1) // 2
        
        l, r = 0, len(nums1)
        while l <= r:
            p1 = (l + r) // 2
            p2 = size - p1
            
            nums1_left  = float('-inf') if p1 == 0 else nums1[p1 - 1]
            nums1_right = float('inf')  if p1 == m else nums1[p1]
            nums2_left  = float('-inf') if p2 == 0 else nums2[p2 - 1]
            nums2_right = float('inf')  if p2 == n else nums2[p2]
            
            if   nums1_left > nums2_right: r = p1 - 1
            elif nums2_left > nums1_right: l = p1 + 1
            else:
                if total & 1: return max(nums1_left, nums2_left)
                return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2

🤖 Java