yokolet's notelets

  1. Sorting and Searching
  2. Median of Two Sorted Arrays

Sorting and Searching

Median of Two Sorted Arrays

Problem Description

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:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10**6 <= nums1[i], nums2[i] <= 10**6

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

Examples

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.

How to Solve

An easy solution is: merge two arrays, sort it then return the middle value(s). However, the problem requires O(log(m + n)) time complexity, which suggests the binary search approach. The binary search indices will be based on the shorter array. The solution starts from the shorter array’s index, mid2 = (low + high) // 2, and the longer array’s index, mid1 = m + n - mid2. Next, values at four indices below are compared:

  • nums1’s middle 2 indices – l1 (left), r1 (right)
  • nums2’s middle 2 indices – l2 (left), r2 (right)

When l1 > r2, the median exists on the left half of nums1. So, the high value should be decreased. When l2 > r1, the median exists on the right half of nums1. So, the low value should be increased. Otherwise, the values for median were found. So, calculate and return the median.

Solution

  • class MedianOfTwoSortedArrays {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size(), n = nums2.size();
            if (m < n) {
                return findMedianSortedArrays(nums2, nums1);
            }
            if (n == 0) {
                return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;
            }
            int low = 0, high = n * 2;
            while (low <= high) {
                int mid2 = (low + high) / 2;
                int mid1 = m + n - mid2;
                int l1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2];
                int l2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2];
                int r1 = mid1 == m * 2 ? INT_MAX : nums1[mid1 / 2];
                int r2 = mid2 == n * 2 ? INT_MAX : nums2[mid2 / 2];
                if (l1 > r2) {
                    low = mid2 + 1;
                } else if (l2 > r1) {
                    high = mid2 - 1;
                } else {
                    return ((l1 < l2 ? l2 : l1) + (r1 < r2 ? r1 : r2)) / 2.0;
                }
            }
            return 0.0;
        }
    };
    
  • 
    
  • 
    
  • class MedianOfTwoSortedArrays:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            m, n = len(nums1), len(nums2)
            if m < n:
              return self.findMedianSortedArrays(nums2, nums1)
            if n == 0:
              return (nums1[(m - 1) // 2] + nums1[m // 2]) / 2.0
            
            low, high = 0, n * 2
            while low <= high:
                mid2 = (low + high) // 2
                mid1 = m + n - mid2
                l1 = float('-inf') if mid1 == 0 else nums1[(mid1 - 1) // 2]
                l2 = float('-inf') if mid2 == 0 else nums2[(mid2 - 1) // 2]
                r1 = float('inf') if mid1 == m * 2 else nums1[mid1 // 2]
                r2 = float('inf') if mid2 == n * 2 else nums2[mid2 // 2]
                if l1 > r2:
                  low = mid2 + 1
                elif l2 > r1:
                  high = mid2 - 1
                else:
                  return (max([l1, l2]) + min([r1, r2])) / 2.0
    
  • # @param {Integer[]} nums1
    # @param {Integer[]} nums2
    # @return {Float}
    
    class Integer
      N_BYTES = [42].pack('i').size
      N_BITS = N_BYTES * 16
      MAX = 2 ** (N_BITS - 2) - 1
      MIN = -MAX - 1
    end
    INT_MIN = Integer::MIN
    INT_MAX = Integer::MAX
    
    def find_median_sorted_arrays(nums1, nums2)
      m = nums1.length
      n = nums2.length
      return find_median_sorted_arrays(nums2, nums1) if m < n
      return (nums1[(m - 1) / 2].to_f + nums1[m / 2].to_f) / 2 if n == 0
    
      lo, hi = 0, n * 2
      while lo <= hi do
        mid2 = (lo + hi) / 2
        mid1 = m + n - mid2
        l1 = (mid1 == 0) ? INT_MIN : nums1[(mid1 - 1) / 2]
        l2 = (mid2 == 0) ? INT_MIN : nums2[(mid2 - 1) / 2]
        r1 = (mid1 == m * 2) ? INT_MAX : nums1[(mid1 / 2)]
        r2 = (mid2 == n * 2) ? INT_MAX : nums2[(mid2 / 2)]
        if l1 > r2
          lo = mid2 + 1
        elsif l2 > r1
          hi = mid2 - 1
        else
          return ([l1, l2].max.to_f + [r1, r2].min.to_f) / 2
        end
      end
    end
    

Complexities

  • Time: O(log(m + n)) – m, n: lengths of two arrays
  • Space: O(1)
Hard
Binary Search
Array