Median of Two Sorted Arrays

Problem Statement

Link: LeetCode

Complexity: Hard

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)).

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.

Constraints:

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

---

Solution Explanation:

References:

• Working with Numpy Arrays

Before we get started, let’s document what all is known about given arrays:

Note:

Input arrays are sorted in ascending order, so are not required to be sorted.

Now, first, we should determine the partition positions for both arrays such that the number of elements on the left side is equal to the number of elements on the right side.

This is done by setting two pointers, i and j, to the midpoints of the two arrays and adjusting their positions based on the comparison of elements at i and j until the partition conditions are satisfied.

Next, we should check if the combined arrays have an odd or even number of elements. If it’s odd, the median is the element at the partition position. If it’s even, the median is the average of the elements at the partition positions.

Let’s take below example:

Let’s consider two sorted arrays nums1 and nums2 of lengths m and n, respectively:

nums1 = [1, 3, 8, 9, 15]
nums2 = [7, 11, 18, 19, 21, 25]

To find the median of the two arrays, we need to split them into two parts at some point. Let’s say we split nums1 at index i and nums2 at index j. Then, the left and right parts of the combined array would look like this:

left_part = nums1[0:i] + nums2[0:j]
right_part = nums1[i:] + nums2[j:]

Iteration 1 – We start by setting two pointers, i and j, to the midpoints of the two arrays.

Iteration 2 – We compare the elements at i and j and adjust the positions of the pointers based on their values. Since nums1[i] < nums2[j], we can infer that the median must be on the right side of nums1[i], so we move i to the right:

Now, we compare the elements again and notice that nums1[i] > nums2[j-1], so the median must be between nums1[i-1] and nums1[i] on the left side and nums2[j-1] and nums2[j] on the right side. We can return the median now since the number of elements on the left and right sides is equal.

If the number of elements in the combined array m+n is odd, the median is simply the maximum of the left parts, which is 8 in this example. If m+n is even, we take the average of the maximum of the left parts and the minimum of the right parts.

---

Solution Code:

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

        low, high = 0, m
        while low <= high:
            i = (low + high) // 2
            j = (m + n + 1) // 2 - i
            if i < m and nums2[j-1] > nums1[i]:
                low = i + 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                high = i - 1
            else:
                if i == 0:
                    max_left = nums2[j-1]
                elif j == 0:
                    max_left = nums1[i-1]
                else:
                    max_left = max(nums1[i-1], nums2[j-1])
                if (m + n) % 2 == 1:
                    return max_left
                if i == m:
                    min_right = nums2[j]
                elif j == n:
                    min_right = nums1[i]
                else:
                    min_right = min(nums1[i], nums2[j])
                return (max_left + min_right) / 2.0

Note

The division operator / returns a float in Python 3, so we need to use the floor division operator // to get integer division.