Quick Overview

Find the median of two already-sorted integer arrays in logarithmic time, including when one array is empty and the result is fractional.

Locate the Middle Value Across Two Sorted Inputs

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Other

### Problem Two integer arrays, `first` and `second`, are already sorted in nondecreasing order. Return the median of the values in their combined multiset, retaining every occurrence of a repeated value. For an odd total count, the median is the central value. For an even total count, it is the arithmetic mean of the two central values and may end in `.5`. The overall algorithm must take `O(log(m + n))` time, where `m` and `n` are the two lengths. A linear merge does not meet that requirement. Preserve the original `findMedianSortedArrays` interface: two integer-array arguments and a floating-point scalar result (`double` in C++ and Java). Do not replace the result with an integer or change the arrays into a different input representation. ### Examples **Example 1** ```text Input: first = [2,8], second = [4] Output: 4.0 ``` The combined order is `[2,4,8]`, whose middle value is `4`. **Example 2** ```text Input: first = [1,5], second = [2,8] Output: 3.5 ``` The central values in `[1,2,5,8]` are `2` and `5`. ### Constraints - `m = first.length` and `n = second.length`. - Each length is between `0` and `1000`. - The total length is between `1` and `2000`; both arrays cannot be empty. - Each element is an integer between `-1000000` and `1000000`. - Both inputs are already sorted; sorting them again is not part of the permitted logarithmic algorithm.

Overview: Find the median of two already-sorted integer arrays in logarithmic time, including when one array is empty and the result is fractional.

You are given two integer arrays, `first` and `second`, each already sorted in nondecreasing order. Treat their values as one combined multiset (every repeated value counts every time it appears) and return the **median** of that multiset. - If the combined count is odd, the median is the single middle value. - If the combined count is even, the median is the arithmetic mean of the two middle values, so it may end in `.5`. Return the median as a floating-point number (`float` in Python, `number` in JavaScript, `double` in Java and C++). Because every element is an integer, the answer is always either an integer or an integer plus `0.5`, so it is exact in floating point. An integer-valued median is still returned as a floating-point value (for example `4.0`). Your algorithm must run in `O(log(m + n))` time, where `m` and `n` are the two array lengths. Merging the arrays (or concatenating and sorting them) is linear or worse and does not meet the requirement. ### Example 1 ```text Input: first = [2, 8], second = [4] Output: 4.0 ``` The combined order is `[2, 4, 8]`; the middle value is `4`. ### Example 2 ```text Input: first = [1, 5], second = [2, 8] Output: 3.5 ``` The combined order is `[1, 2, 5, 8]`; the two middle values are `2` and `5`, whose mean is `3.5`. ### Constraints - `m == first.length`, `n == second.length` - `0 <= m <= 1000`, `0 <= n <= 1000` - `1 <= m + n <= 2000` (the two arrays are never both empty) - `-10^6 <= first[i], second[j] <= 10^6` - `first` and `second` are each sorted in nondecreasing order - Required time complexity: `O(log(m + n))`

Constraints

  • m == first.length, n == second.length
  • 0 <= m <= 1000 and 0 <= n <= 1000
  • 1 <= m + n <= 2000 (the two arrays are never both empty)
  • -10^6 <= first[i], second[j] <= 10^6
  • first and second are each sorted in nondecreasing order
  • The algorithm must run in O(log(m + n)) time; a linear merge does not qualify

Examples

Input: ([2, 8], [4])

Expected Output: 4.0

Input: ([1, 5], [2, 8])

Expected Output: 3.5

Hints

  1. You never need the merged array, only the boundary between its smaller half and its larger half. Taking i values from one array fixes how many values must come from the other.
  2. Search over the shorter array. A choice of cuts is right exactly when the largest value left of each cut is no greater than the smallest value right of the other cut.
  3. Treat a cut at the very start or end of an array as having negative or positive infinity on its empty side, so empty arrays and lopsided splits need no special case.

Loading coding console...

Show the approach

Approach

Let a be the shorter array (swap if needed), with m <= n, and let half = (m + n + 1) // 2 be the size of the lower half of the combined multiset. Binary search the number i of elements taken from a for the lower half (0 <= i <= m); the remaining j = half - i come from b. Compare the four boundary values aLeft = a[i-1], aRight = a[i], bLeft = b[j-1], bRight = b[j], using -infinity/+infinity when an index falls off an end. If aLeft <= bRight and bLeft <= aRight, every value in the lower half is <= every value in the upper half, so the cut is the true median split: for an odd total the median is max(aLeft, bLeft), and for an even total it is (max(aLeft, bLeft) + min(aRight, bRight)) / 2. If aLeft > bRight, too many elements were taken from a, so move the search left (hi = i - 1); otherwise too few were taken, so move right (lo = i + 1). Because a is sorted, these conditions are monotone in i, so binary search finds the unique valid split. Searching over the shorter array keeps j inside [0, n]. Each step is O(1), giving O(log(min(m, n))) time, which is within O(log(m + n)), and O(1) extra space. Values never exceed 10^6 in magnitude, so the sum of the two middle values fits in a 32-bit integer; the Java and C++ references widen to 64 bits only so the infinity sentinels compare safely.

Time complexity:
O(log(min(m, n)))
Space complexity:
O(1)