Skip to content

4. Median of Two Sorted Arrays (Hard)

Pyodide

Editor (session: default) Run 
# Type here
Output Clear

Run

Editor (session: default) Run 
class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        A, B = nums1, nums2
        m, n = len(A), len(B)

        if m > n:
            A, B = B, A
            m, n = n, m

        half_len = (m + n + 1) // 2

        low = 0
        high = m

        while low <= high:
            partitionA = (low + high) // 2
            partitionB = half_len - partitionA

            maxLeftA = A[partitionA - 1] if partitionA > 0 else float('-inf')
            minRightA = A[partitionA] if partitionA < m else float('inf')

            maxLeftB = B[partitionB - 1] if partitionB > 0 else float('-inf')
            minRightB = B[partitionB] if partitionB < n else float('inf')

            if maxLeftA <= minRightB and maxLeftB <= minRightA:
                if (m + n) % 2 == 1:
                    return max(maxLeftA, maxLeftB)
                else:
                    return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

            elif maxLeftA > minRightB:
                high = partitionA - 1

            else:
                low = partitionA + 1

        return 0.0

# Example Usage:
sol = Solution()
print(sol.findMedianSortedArrays([1, 3], [2]))       # Output: 2.0
print(sol.findMedianSortedArrays([1, 2], [3, 4]))    # Output: 2.5
print(sol.findMedianSortedArrays([0, 0], [0, 0]))    # Output: 0.0
Output Clear

Solution

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

        if m > n:
            A, B = B, A
            m, n = n, m

        half_len = (m + n + 1) // 2

        low = 0
        high = m

        while low <= high:
            partitionA = (low + high) // 2
            partitionB = half_len - partitionA

            maxLeftA = A[partitionA - 1] if partitionA > 0 else float('-inf')
            minRightA = A[partitionA] if partitionA < m else float('inf')

            maxLeftB = B[partitionB - 1] if partitionB > 0 else float('-inf')
            minRightB = B[partitionB] if partitionB < n else float('inf')

            if maxLeftA <= minRightB and maxLeftB <= minRightA:
                if (m + n) % 2 == 1:
                    return max(maxLeftA, maxLeftB)
                else:
                    return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

            elif maxLeftA > minRightB:
                high = partitionA - 1

            else:
                low = partitionA + 1

        return 0.0

Function Description

Source code in python/_4.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        """
        Finds the median of two sorted arrays $nums1$ and $nums2$.

        This method merges the problem of finding the median into a search problem 
        by using binary search to find the correct partition point in the smaller array.
        The goal is to partition both arrays, $A$ and $B$, such that:
        1. The total number of elements in the left partition is $\lfloor (m+n+1)/2 \rfloor$.
        2. $\max(Left\_A) \le \min(Right\_B)$ and $\max(Left\_B) \le \min(Right\_A)$.



        The median is then calculated based on whether the total length is odd or even:
        - **Odd length:** $\max(\max(Left\_A), \max(Left\_B))$
        - **Even length:** $(\max(\max(Left\_A), \max(Left\_B)) + \min(\min(Right\_A), \min(Right\_B))) / 2$

        The time complexity is $O(\log(\min(m, n)))$ because the binary search is 
        performed on the smaller array.

        Args:
            nums1: The first sorted list of integers.
            nums2: The second sorted list of integers.

        Returns:
            The median of the two sorted arrays as a float.

        Examples:
            >>> sol = Solution()
            >>> sol.findMedianSortedArrays([1, 3], [2])
            2.0
            >>> sol.findMedianSortedArrays([1, 2], [3, 4])
            2.5
            >>> sol.findMedianSortedArrays([1, 3, 8, 9, 15], [7, 11, 18, 19, 21, 25])
            11.0
        """
        A, B = nums1, nums2
        m, n = len(A), len(B)

        if m > n:
            A, B = B, A
            m, n = n, m

        half_len = (m + n + 1) // 2

        low = 0
        high = m

        while low <= high:
            partitionA = (low + high) // 2
            partitionB = half_len - partitionA

            maxLeftA = A[partitionA - 1] if partitionA > 0 else float('-inf')
            minRightA = A[partitionA] if partitionA < m else float('inf')

            maxLeftB = B[partitionB - 1] if partitionB > 0 else float('-inf')
            minRightB = B[partitionB] if partitionB < n else float('inf')

            if maxLeftA <= minRightB and maxLeftB <= minRightA:
                if (m + n) % 2 == 1:
                    return max(maxLeftA, maxLeftB)
                else:
                    return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

            elif maxLeftA > minRightB:
                high = partitionA - 1

            else:
                low = partitionA + 1

        return 0.0

findMedianSortedArrays(nums1, nums2)

Finds the median of two sorted arrays \(nums1\) and \(nums2\).

This method merges the problem of finding the median into a search problem by using binary search to find the correct partition point in the smaller array. The goal is to partition both arrays, \(A\) and \(B\), such that: 1. The total number of elements in the left partition is \(\lfloor (m+n+1)/2 floor\). 2. \(\max(Left\_A) \le \min(Right\_B)\) and \(\max(Left\_B) \le \min(Right\_A)\).

The median is then calculated based on whether the total length is odd or even: - Odd length: \(\max(\max(Left\_A), \max(Left\_B))\) - Even length: \((\max(\max(Left\_A), \max(Left\_B)) + \min(\min(Right\_A), \min(Right\_B))) / 2\)

The time complexity is \(O(\log(\min(m, n)))\) because the binary search is performed on the smaller array.

Parameters:

Name Type Description Default
nums1 list[int]

The first sorted list of integers.

 required
nums2 list[int]

The second sorted list of integers.

 required

Returns:

Type Description
float

The median of the two sorted arrays as a float.

Examples:

>>> sol = Solution()
>>> sol.findMedianSortedArrays([1, 3], [2])
2.0
>>> sol.findMedianSortedArrays([1, 2], [3, 4])
2.5
>>> sol.findMedianSortedArrays([1, 3, 8, 9, 15], [7, 11, 18, 19, 21, 25])
11.0
Source code in python/_4.py 
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
    """
    Finds the median of two sorted arrays $nums1$ and $nums2$.

    This method merges the problem of finding the median into a search problem 
    by using binary search to find the correct partition point in the smaller array.
    The goal is to partition both arrays, $A$ and $B$, such that:
    1. The total number of elements in the left partition is $\lfloor (m+n+1)/2 \rfloor$.
    2. $\max(Left\_A) \le \min(Right\_B)$ and $\max(Left\_B) \le \min(Right\_A)$.



    The median is then calculated based on whether the total length is odd or even:
    - **Odd length:** $\max(\max(Left\_A), \max(Left\_B))$
    - **Even length:** $(\max(\max(Left\_A), \max(Left\_B)) + \min(\min(Right\_A), \min(Right\_B))) / 2$

    The time complexity is $O(\log(\min(m, n)))$ because the binary search is 
    performed on the smaller array.

    Args:
        nums1: The first sorted list of integers.
        nums2: The second sorted list of integers.

    Returns:
        The median of the two sorted arrays as a float.

    Examples:
        >>> sol = Solution()
        >>> sol.findMedianSortedArrays([1, 3], [2])
        2.0
        >>> sol.findMedianSortedArrays([1, 2], [3, 4])
        2.5
        >>> sol.findMedianSortedArrays([1, 3, 8, 9, 15], [7, 11, 18, 19, 21, 25])
        11.0
    """
    A, B = nums1, nums2
    m, n = len(A), len(B)

    if m > n:
        A, B = B, A
        m, n = n, m

    half_len = (m + n + 1) // 2

    low = 0
    high = m

    while low <= high:
        partitionA = (low + high) // 2
        partitionB = half_len - partitionA

        maxLeftA = A[partitionA - 1] if partitionA > 0 else float('-inf')
        minRightA = A[partitionA] if partitionA < m else float('inf')

        maxLeftB = B[partitionB - 1] if partitionB > 0 else float('-inf')
        minRightB = B[partitionB] if partitionB < n else float('inf')

        if maxLeftA <= minRightB and maxLeftB <= minRightA:
            if (m + n) % 2 == 1:
                return max(maxLeftA, maxLeftB)
            else:
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

        elif maxLeftA > minRightB:
            high = partitionA - 1

        else:
            low = partitionA + 1

    return 0.0

Explanation

You are given two integer arrays, nums1 and nums2, with sizes \(m\) and \(n\) respectively. Both arrays are already sorted in ascending order. The task is to find and return the median value of the two sorted arrays when they are combined. This problem is classified as Hard due to the strict time complexity requirement for the optimal solution.

The median is defined as the middle value in an ordered list of numbers. If the total number of elements, \(m+n\), is odd, the median is the single middle element. If the total number of elements is even, the median is the average (mean) of the two middle elements. For instance, for [1, 2, 3], the median is \(2\); for [1, 2, 3, 4], the median is \((2+3)/2 = 2.5\).

The most crucial constraint is that your algorithm's overall run time complexity must be \(O(\log(m+n))\) or better, typically achieved with \(O(\log(\min(m, n)))\). This logarithmic constraint prevents a simple \(O(m+n)\) solution that would merge both arrays entirely before calculating the median. Instead, the optimal solution leverages the sorted nature of the arrays and employs a binary search approach to efficiently find the correct partition point that isolates the elements needed to compute the median.