Problem Statement in English

You’re given two sorted arrays nums1 and nums2 of size m and n respectively. Return the median of the two sorted arrays.

Your algorithm should run in $O(log (m+n))$ time.

Approach

Had there been no time complexity constraint, we could have merged the two arrays and found the median in $O(m+n)$ time. However, since we are required to find the median in $O(log (m+n))$ time, we’re going to need to do better.

We’re going to have to virtually create a merged array and find the median without actually merging the two arrays.

Here’s a mental picture of how we’re going to do it:

nums1:  [ 1,  3,  8  |  9, 15 ]          <-- Cut after index 3
nums2:  [ 7, 11      | 18, 19, 21, 25 ]  <-- Cut after index 2
        ------------   ----------------
         Left Group       Right Group
         (6 items)         (5 items)

And once we have this virtual split, we can figure out which element or elements from each side are going to interact and give us the median, using a simple max/min comparison.

Now how do we do the actual splitting? Since we know the length of the 2 arrays combined, we know what the midpoint should be. In other words we know how many elements should be in the left group and how many should be in the right group.

So if we find the index to split the first array, the index to split the second array is simply the midpoint minus the split index of the first array.

How do we find that split index? We can use binary search on the smaller of the two arrays to find the correct split index.

Why the smaller of the two arrays? Because if we split the larger array, we may end up with a split index that is out of bounds for the smaller array. By splitting the smaller array, we ensure that the split index for the larger array will always be valid.

Solution in Python


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)

        if m > n:
            nums1, nums2 = nums2, nums1
            m, n = n, m

        low, high = 0, m
        half = (m + n + 1) // 2

        while low <= high:
            i = (low + high) // 2
            j = half - i

            max_left1 = -inf if i == 0 else nums1[i - 1]
            min_right1 = inf if i == m else nums1[i]
            max_left2 = -inf if j == 0 else nums2[j - 1]
            min_right2 = inf if j == n else nums2[j]
            
            if max_left1 <= min_right2 and max_left2 <= min_right1:
                if (m + n) % 2:
                    return max(max_left1, max_left2)
                else:
                    return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
            elif max_left1 > min_right2:
                high = i - 1
            else:
                low = i + 1

Complexity

  • Time: $O(\log(\min(m,n)))$
    Since we are performing a binary search on the smaller of the two arrays, the time complexity is logarithmic with respect to the size of the smaller array.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables and not using any additional data structures that scale with input size, the space complexity is constant.

Mistakes I Made

I had to look this up :(

And we are done.