# 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

# Solution

Approach 1: use 2 pointers to merge 2 sorted arrays, counting items up until the (M + N) / 2th. Running time O(M + N), where M and N are the array lengths.

Approach 2: for each item in nums1, find its insert position in nums2 (using binary search), and see if insert position_in_nums2 + its_own_index_in_nums1 == (M + N) / 2. Do the same for each item in nums2 (insert back to nums1). If M + N is even, then look for 2 numbers: (M + N) / 2 and (M + N) / 2 + 1, then take the average. Running time O(Mlog(N)) + O(Nlog(M)).

Approach 3: Solve the problem of finding the kth smallest element in 2 sorted arrays. This can be done by comparing the the k/2th smallest items in both arrays, then eliminating k/2 items from one of the arrays. Running time O(log(M + N)).

# Code (Python)

Approach 3:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if (len(nums1) + len(nums2)) % 2 == 1:
            return self.find_kth_smallest_in_two_sorted_arrays(
                nums1,
                nums2,
                (len(nums1) + len(nums2)) // 2 + 1
            )
        else:
            return (
                self.find_kth_smallest_in_two_sorted_arrays(
                    nums1,
                    nums2,
                    (len(nums1) + len(nums2)) // 2
                ) +
                self.find_kth_smallest_in_two_sorted_arrays(
                    nums1,
                    nums2,
                    (len(nums1) + len(nums2)) // 2 + 1
                )
            ) / 2
    
    def find_kth_smallest_in_two_sorted_arrays(self, nums1, nums2, k):
        # make sure nums1 is shorter than nums2
        if len(nums1) > len(nums2):
            return self.find_kth_smallest_in_two_sorted_arrays(nums2, nums1, k)
        # 2 base cases
        if len(nums1) == 0:
            return nums2[k-1]
        if k == 1:
            return min(nums1[0], nums2[0])
        # eliminates roughly k/2 items each time by comparing the k/2 smallest item in each array
        index1 = min(len(nums1), k // 2)
        index2 = k - index1
        if nums1[index1 - 1] <= nums2[index2 - 1]:
            # rule out nums1[0:index1], because nums1[index1-1] is at most larger than 2 * (k/2 - 1) items, so it can't be the kth smallest in both arrays combined
            # should really pass just the start index and not do this array slicing, because slicing takes linear time
            return self.find_kth_smallest_in_two_sorted_arrays(nums1[index1:], nums2, index2)
        else:
            return self.find_kth_smallest_in_two_sorted_arrays(nums1, nums2[index2:], index1)

# Code (C++)

Approach 1:

// O(m+n)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<int> res;
        int i1 = 0;
        int i2 = 0;
        while (i1 < n1 || i2 < n2)
        {
            if (i1 >= n1 || (i2 < n2 && nums1[i1] > nums2[i2]))
            {
                res.push_back(nums2[i2]);
                i2++;
            }
            else
            {
                res.push_back(nums1[i1]);
                i1++;
            }
        }
        int n3 = res.size();
        if (n3 % 2 != 0)
            return res[n3/2];
        else
            return (double)(res[n3/2] + res[n3/2-1]) / 2;
    }
};

Approach 3:

// O(log(m+n))
class Solution {
private:
    int getKth(vector<int>& nums1, vector<int>& nums2, int head1, int head2, int k) {
        if (head1 >= nums1.size())
            return nums2[head2+k-1];
        if (head2 >= nums2.size())
            return nums1[head1+k-1];
        if (k == 1)
            return std::min(nums1[head1], nums2[head2]);
        if (head2+k/2-1 >= nums2.size() ||
            head1+k/2-1 < nums1.size() && nums1[head1+k/2-1] <= nums2[head2+k/2-1])
            return getKth(nums1, nums2, head1+k/2, head2, k-k/2);
        else
            return getKth(nums1, nums2, head1, head2+k/2, k-k/2);
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        if (len % 2 != 0)
            return getKth(nums1, nums2, 0, 0, len/2+1);
        else
            return (double)(
                getKth(nums1, nums2, 0, 0, len/2) +
                getKth(nums1, nums2, 0, 0, len/2+1))
                / 2;
    }
};