Median of All Values Across Several Sorted Integer Arrays
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given several integer arrays, each sorted in non-decreasing order. Return the median of all of their elements taken together.
The question was first asked for exactly two sorted arrays, and the follow-up asked for the same result when there are many input arrays. Implement the general version: the function receives any number of arrays, and two arrays is the original question.
### Function Signature
```python
def median_of_sorted_arrays(arrays: list[list[int]]) -> float:
```
### Rules
- Let `N` be the total number of elements across all arrays, and let `merged` be all of those elements in sorted order, with duplicates kept.
- If `N` is odd, the median is `merged[N // 2]`. If `N` is even, the median is `(merged[N // 2 - 1] + merged[N // 2]) / 2`.
- Return the median as a float, for example `3.0` rather than `3`. Every possible median is an integer or an integer plus one half, so the result is exact.
- Any individual array may be empty, but there is at least one element in total.
### Constraints
- `1 <= len(arrays) <= 10^4`
- `0 <= len(arrays[i])` for every `i`, and `1 <= N <= 2 * 10^5`
- Each `arrays[i]` is sorted in non-decreasing order.
- `-10^9 <= arrays[i][j] <= 10^9`
### Examples
**Example 1**
```text
Input: arrays = [[1, 4], [2, 9]]
Output: 3.0
```
All elements in order are `[1, 2, 4, 9]`. `N = 4` is even, so the median is the average of `2` and `4`.
**Example 2**
```text
Input: arrays = [[-3, 5, 5], [0]]
Output: 2.5
```
All elements in order are `[-3, 0, 5, 5]`, and the average of `0` and `5` is `2.5`.
**Example 3**
```text
Input: arrays = [[-5, 0, 7], [], [2, 2, 9], [4, 10, 11]]
Output: 4.0
```
All elements in order are `[-5, 0, 2, 2, 4, 7, 9, 10, 11]`. `N = 9` is odd, so the median is the element at index `4`, which is `4`. The empty array contributes nothing.
Overview: Given any number of integer arrays, each sorted in non-decreasing order, return the median of all their elements combined, averaging the two middle values when the total count is even. It tests order-statistic reasoning over sorted inputs, starting from two arrays and generalizing to many.
You are given `arrays`, a list of integer arrays, each sorted in non-decreasing order. Return the median of all of their elements taken together.
This question was first asked for exactly two sorted arrays, and the follow-up asked for the same result when there are many input arrays. Implement the general version: the function receives any number of arrays, and two arrays is the original question.
**Rules**
- Let `N` be the total number of elements across all arrays, and let `merged` be all of those elements in sorted order, with duplicates kept.
- If `N` is odd, the median is `merged[N // 2]` (0-indexed). If `N` is even, the median is `(merged[N // 2 - 1] + merged[N // 2]) / 2`.
- Return the median as a floating-point number (a `float` in Python, a `double` in Java and C++, a number in JavaScript), for example `3.0` rather than `3`. Every possible median is an integer or an integer plus one half, so the result is exact.
- Any individual array may be empty, but there is at least one element in total.
Every element, and the sum of the two middle elements, fits in a signed 32-bit integer: that sum has absolute value at most `2 * 10^9`, which is below `2^31 - 1`.
**Example 1**
```text
Input: arrays = [[1, 4], [2, 9]]
Output: 3.0
```
All elements in order are `[1, 2, 4, 9]`. `N = 4` is even, so the median is the average of `2` and `4`.
**Example 2**
```text
Input: arrays = [[-5, 0, 7], [], [2, 2, 9], [4, 10, 11]]
Output: 4.0
```
All elements in order are `[-5, 0, 2, 2, 4, 7, 9, 10, 11]`. `N = 9` is odd, so the median is the element at index `4`, which is `4`. The empty array contributes nothing.
**Constraints**
- `1 <= len(arrays) <= 10^4`
- `0 <= len(arrays[i])` for every `i`, and `1 <= N <= 2 * 10^5`
- Each `arrays[i]` is sorted in non-decreasing order.
- `-10^9 <= arrays[i][j] <= 10^9`
Constraints
- 1 <= len(arrays) <= 10^4
- 0 <= len(arrays[i]) for every i, and 1 <= N <= 2 * 10^5
- Each arrays[i] is sorted in non-decreasing order.
- -10^9 <= arrays[i][j] <= 10^9
Examples
Input: ([[1, 4], [2, 9]],)
Expected Output: 3.0
Explanation: Source Example 1: merged [1, 2, 4, 9], N = 4 is even and the two middles 2 and 4 come from different arrays; an integer median is returned as 3.0.
Input: ([[-3, 5, 5], [0]],)
Expected Output: 2.5
Explanation: Source Example 2: merged [-3, 0, 5, 5]; the average of 0 and 5 is 2.5.
Hints
- Only one position of the combined sorted order matters when N is odd (index N // 2), and two adjacent positions when N is even (N // 2 - 1 and N // 2). Work out N first.
- Every input array is already sorted, and any of them may be empty; plan how you reach those middle positions without assuming each array has a first element.
- Duplicates count separately, and the even-N average must keep its half: the average of -2 and -1 is -1.5, not -1 or -2.