#4

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Median of Two Sorted Arrays

Find the median of two sorted arrays using binary search for efficient O(log(min(m, n))) time complexity.

Problem Statement

Given two sorted arrays, nums1 and nums2, of sizes m and n respectively, find the median of the two sorted arrays. The merged array of both should be in non-decreasing order. The overall runtime complexity should be O(log(m+n)).

For example, when nums1 = [1,3] and nums2 = [2], the correct output is 2.0 as the median. The goal is to find a solution that avoids merging the arrays entirely, but instead utilizes a binary search approach over the valid answer space.

Examples

Example 1

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

Output: 2.00000

merged array = [1,2,3] and median is 2.

Example 2

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

Output: 2.50000

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 Approach

Binary Search Over the Smaller Array

To find the median without merging the arrays, perform binary search on the smaller of the two arrays, nums1 and nums2. This limits the search space, ensuring that you efficiently narrow down the correct partition to find the median.

Partition the Arrays

Divide both arrays into two parts where the left part contains smaller elements and the right part contains larger ones. The goal is to balance these partitions such that the left partition contains the same number of elements (or one more) than the right partition.

Handle Even and Odd Lengths

If the total length of the merged arrays is odd, the median is the maximum of the left partition. If even, it's the average of the maximum of the left partition and the minimum of the right partition.

Complexity Analysis

Metric	Value
Time	O(\log(\min(m, n)))
Space	O(1)

The time complexity of this solution is O(log(min(m, n))) because we perform binary search on the smaller of the two arrays. The space complexity is O(1) since we only use a few variables to track the partition points.

What Interviewers Usually Probe

The candidate demonstrates a clear understanding of binary search over a valid answer space.
The candidate can explain how the partitioning logic helps in avoiding unnecessary merging of arrays.
The candidate can handle edge cases, like odd or even total lengths, while maintaining time efficiency.

Common Pitfalls or Variants

Common pitfalls

Confusing partitioning logic can lead to incorrect median calculations.
Failing to account for edge cases where one array is empty or the partitioning is imbalanced.
Over-complicating the solution by attempting to merge the arrays instead of using binary search.

Follow-up variants

Handling arrays with significantly different lengths (m << n or n << m).
Solving the problem with multiple edge cases like empty arrays.
Optimizing for very large input arrays (up to 2000 elements).

FAQ

How do I approach the 'Median of Two Sorted Arrays' problem?

Use binary search over the smaller array to partition the arrays such that the left side has equal or one more element than the right side. Then, find the median by comparing the partition elements.

What is the time complexity of this solution?

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

What happens if one of the arrays is empty?

If one of the arrays is empty, the solution reduces to finding the median of the non-empty array.

How do I find the median when the total length is even?

When the total length is even, the median is the average of the maximum element in the left partition and the minimum element in the right partition.

What if the input arrays are very large?

The algorithm still works efficiently for large arrays, with O(log(min(m, n))) time complexity, which ensures that even large inputs can be handled quickly.

terminal

Solution

Solution 1: Divide and Conquer

The problem requires the time complexity of the algorithm to be $O(\log (m + n))$, so we cannot directly traverse the two arrays, but need to use the binary search method.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def f(i: int, j: int, k: int) -> int:
            if i >= m:
                return nums2[j + k - 1]
            if j >= n:
                return nums1[i + k - 1]
            if k == 1:
                return min(nums1[i], nums2[j])
            p = k // 2
            x = nums1[i + p - 1] if i + p - 1 < m else inf
            y = nums2[j + p - 1] if j + p - 1 < n else inf
            return f(i + p, j, k - p) if x < y else f(i, j + p, k - p)

        m, n = len(nums1), len(nums2)
        a = f(0, 0, (m + n + 1) // 2)
        b = f(0, 0, (m + n + 2) // 2)
        return (a + b) / 2

Continue Practicing

#240 search a 2d matrix ii #315 count of smaller numbers after self #327 count of range sum