# Median of Two Sorted Arrays

##### Problem Statement

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 = 
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:

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.
Scroll to Top