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

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

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 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.

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Input: nums1 = [2], nums2 = []
Output: 2.00000

💡 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

class Solution {
    /**
     * @time  : O(log(min(m,n)))
     * @space : O(1)
     */
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int size  = (total + 1) / 2;
        
        int l = 0, r = m;
        while(l <= r) {
            int p1 = (l + r) / 2;
            int p2 = size - p1;
            
            int num1_left  = (p1 == 0) ? Integer.MIN_VALUE : nums1[p1 - 1];
            int num1_right = (p1 == m) ? Integer.MAX_VALUE : nums1[p1];
            int num2_left  = (p2 == 0) ? Integer.MIN_VALUE : nums2[p2 - 1];
            int num2_right = (p2 == n) ? Integer.MAX_VALUE : nums2[p2];
            
            if      (num1_left > num2_right) r = p1 - 1;
            else if (num2_left > num1_right) l = p1 + 1;
            else {
                if(total % 2 != 0) return (double) Math.max(num1_left, num2_left);
                return ((double)Math.max(num1_left, num2_left) + Math.min(num1_right, num2_right)) / 2;
            }
        }
        
        return -1;
    }
}