4. Median of Two Sorted Arrays

Posted on 2 mins read

1. Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

2. Follow Up

The overall run time complexity should be O(log (m+n)).

3. Example

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.

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

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

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

4. 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$

5. Solutions

My Accepted Solution(Follow Up)

m = i_nums1.size(), n = i_nums2.size()
Time complexity: $O(lg_2(m + n))$
Space complexity: $O(lg_2(m + n))$

// we need to solve the problem in lg time complexity, so we need to use binary search

class Solution 
{
private:
    int findKthNumber(const vector<int>& i_nums1, int index1, const vector<int>& i_nums2, int index2, int k) 
    {
        if(index1 >= i_nums1.size()) return i_nums2[index2 + k - 1];
        if(index2 >= i_nums2.size()) return i_nums1[index1 + k - 1];
        if(k == 1) return min(i_nums1[index1], i_nums2[index2]);
        
        int median1 = (index1 + k/2 - 1 < i_nums1.size()) ? i_nums1[index1 + k/2 - 1] : INT_MAX;
        int median2 = (index2 + k/2 - 1 < i_nums2.size()) ? i_nums2[index2 + k/2 - 1] : INT_MAX;
        
        // we need to pass the array with less median, since it ensures that we will not leave out the median value
        return (median1 < median2 ? findKthNumber(i_nums1, index1 + k/2, i_nums2, index2, k - k/2)
               : findKthNumber(i_nums1, index1, i_nums2, index2 + k/2, k - k/2));
    }
public: 
    // double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    double findMedianSortedArrays(const vector<int>& i_nums1, const vector<int>& i_nums2) 
    {
        // if total number of i_nums1's nodes and i_nums2's nodes is odd, leftMedian and rightMedian will be the same value
        int leftMedianIndex = (i_nums1.size() + i_nums2.size() + 1) / 2;
        int rightMedianIndex = (i_nums1.size() + i_nums2.size() + 2) / 2;
        
        int leftMedian = findKthNumber(i_nums1, 0, i_nums2, 0, leftMedianIndex);
        int rightMedian = (leftMedianIndex == rightMedianIndex ? leftMedian : findKthNumber(i_nums1, 0, i_nums2, 0, rightMedianIndex));
        
        return (leftMedian + rightMedian) / 2.0; 
    }
};

5.1 Binary Search - Iteration Style(Follow Up)

// 
// Time complexity : 
// Space complexity : 

// TO DO
comments powered by Disqus