The Question

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the combined sorted arrays. The solution must provide an overall run-time complexity of O(log(m+n)). Example: Input: nums1 = [1, 3], nums2 = [2] Output: 2.00000 Explanation: Combined array = [1, 2, 3] and median is 2. Input: nums1 = [1, 2], nums2 = [3, 4] Output: 2.50000 Explanation: Combined array = [1, 2, 3, 4] and median is (2 + 3) / 2 = 2.5. Constraints: - 0 <= m, n <= 1000 - 1 <= m + n <= 2000 - -10^6 <= nums1[i], nums2[i] <= 10^6

Java

Binary Search

Questions & Insights

Clarifying Questions

What are the constraints on the sizes of

nums1

and

nums2

? (e.g.,

0 \le m, n \le 1000

)

Is it guaranteed that the total number of elements

m+n \ge 1

Should the time complexity be strictly logarithmic

O(\log(m+n))

or is linear

O(m+n)

acceptable? (Assumption:

O(\log(\min(m, n)))

is required for a Staff-level solution).

How should we handle integer overflow for very large array indices? (Assumption: Standard integer range is sufficient for array indexing).

Assumptions:

nums1

and

nums2

are sorted in non-decreasing order.

The solution must achieve

O(\log(\min(m, n)))

time complexity.

m+n

is even, the median is the average of the two middle elements.

Thinking Process

Partitioning Strategy: Instead of merging the arrays, we aim to find a partition point in both arrays such that the total number of elements on the left side equals the total number of elements on the right side (or one more if the total count is odd).

Binary Search on Indices: We perform binary search on the indices of the smaller array to find the split point. We define i as the split in nums1 and calculate j in nums2 such that

i + j = \frac{m + n + 1}{2}

Boundary Verification: A partition is valid if the largest element on the left of both arrays is less than or equal to the smallest element on the right of both arrays (

L1 \le R2

and

L2 \le R1

Handling Edge Cases: Use

-\infty

and to handle cases where the partition falls at the very beginning or end of an array.

Implementation Breakdown

Problem Set

Functional Requirements: Find the median of two sorted arrays.

Constraints:

nums1.length = m

nums2.length = n

0 \le m, n \le 1000

1 \le m + n \le 2000

Time Complexity:

O(\log(\min(m, n)))

Space Complexity:

O(1)

Approach

Algorithm: Binary Search on the partition index.

Data Structure: Arrays.

Complexity:

Time:

O(\log(\min(m, n)))

because we always binary search on the smaller array.

Space:

O(1)

as we only store a few pointer variables.

Implementation

Wrap Up

Advanced Topics

Readability vs Performance: While

O(\log(\min(m, n)))

is mathematically superior, for very small array sizes (e.g.,

n < 50

), a simple linear merge might actually be faster due to cache locality and lower constant factors.

Generalization: This problem can be generalized to finding the

k

-th element of

N

sorted arrays. This would typically involve a Min-Priority Queue or a more complex binary search on the value range.

Large Scale Adaptation: If the arrays were too large to fit in memory and were stored across multiple machines, we could use a distributed selection algorithm (like "Fast Selection" or a distributed version of this binary search) where we communicate only the pivot values and counts.