Median Across Two Arrays

Hard

You have two integer arrays left and right, each sorted in non-decreasing order. Either of them may be empty, but not both. Return the median of all the numbers from both arrays taken together: with an odd total count it is the middle element of the combined sorted sequence, with an even count it is the mean of the two middle elements. The answer is a float. With m and n being the array lengths, aim for O(log(m + n)) time.

Example 1

left=[2, 9], right=[4, 5, 11] → 5.0

Together they form [2, 4, 5, 9, 11]; the middle element is 5.

Example 2

left=[-6, 0, 8], right=[1] → 0.5

Together: [-6, 0, 1, 8]. The count is even, so the median is the mean of the two central values: (0 + 1) / 2 = 0.5.

Example 3

left=[], right=[3, 7] → 5.0

The first array is empty; the median of the second is (3 + 7) / 2 = 5.

Constraints

0 ≤ len(left) ≤ 1000
0 ≤ len(right) ≤ 1000
1 ≤ len(left) + len(right) ≤ 2000
-10⁶ ≤ left[i], right[i] ≤ 10⁶
Both arrays are sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Divide and Conquer

Similar problems

Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Triples Both Rankings Agree On Hard

Input

left=[2, 9], right=[4, 5, 11]

Expected

5.0

Run checks the first 3 tests in your browser. Submit checks all 108 tests on the server, hidden ones included.