Merge K Individually Sorted Integer Arrays Into One Sorted Array
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given `k` arrays of integers, each sorted in non-decreasing order. Return a single array that contains every element of every input array, keeping duplicates, in non-decreasing order.
The interviewer asked for this merge to be built with two named techniques, the two-pointer method and divide and conquer. The console checks only the returned array.
### Function Signature
```python
def merge_sorted_arrays(arrays: list[list[int]]) -> list[int]:
```
### Rules
- The output length equals the total number of elements across all input arrays, and each value appears as many times in the output as it does across all inputs together.
- Any array may be empty, and so may the list of arrays. If there are no elements at all, return `[]`.
### Constraints
- `0 <= len(arrays) <= 10^4`
- `0 <= len(arrays[i])`, and the total number of elements across all arrays is at most `10^5`.
- `-10^9 <= arrays[i][j] <= 10^9`
- Each `arrays[i]` is sorted in non-decreasing order.
### Examples
**Example 1**
```text
Input: arrays = [[1, 4, 9], [2, 2, 7], [3]]
Output: [1, 2, 2, 3, 4, 7, 9]
```
**Example 2**
```text
Input: arrays = [[], [-5, 0], [], [-5, 10]]
Output: [-5, -5, 0, 10]
```
Empty arrays contribute nothing, and the duplicate `-5` is kept.
**Example 3**
```text
Input: arrays = []
Output: []
```
Overview: Merge k integer arrays, each sorted in non-decreasing order, into one sorted array that keeps every duplicate. The interviewer asked for the two-pointer method and divide and conquer, so the problem tests merging sorted sequences and how the cost grows with the number of arrays.
You are given `k` arrays of integers, `arrays`, each sorted in non-decreasing order. Return a single array that contains every element of every input array, keeping duplicates, in non-decreasing order.
The interviewer asked for this merge to be built with two named techniques, the two-pointer method and divide and conquer. The console checks only the returned array.
**Rules**
- The output length equals the total number of elements across all input arrays, and each value appears as many times in the output as it does across all inputs together.
- Any array may be empty, and so may the list of arrays. If there are no elements at all, return `[]`.
**Constraints**
- `0 <= len(arrays) <= 10^4`
- `0 <= len(arrays[i])`, and the total number of elements across all arrays is at most `10^5`.
- `-10^9 <= arrays[i][j] <= 10^9`. Every input and output value fits in a signed 32-bit integer (none can exceed 2^31 - 1), so `int` is sufficient in Java and C++.
- Each `arrays[i]` is sorted in non-decreasing order.
**Example 1**
```text
Input: arrays = [[1, 4, 9], [2, 2, 7], [3]]
Output: [1, 2, 2, 3, 4, 7, 9]
```
**Example 2**
```text
Input: arrays = [[], [-5, 0], [], [-5, 10]]
Output: [-5, -5, 0, 10]
```
Empty arrays contribute nothing, and the duplicate `-5` is kept.
Constraints
- 0 <= len(arrays) <= 10^4
- 0 <= len(arrays[i]), and the total number of elements across all arrays is at most 10^5
- -10^9 <= arrays[i][j] <= 10^9 (every value fits in a signed 32-bit integer)
- Each arrays[i] is sorted in non-decreasing order
Examples
Input: ([[1, 4, 9], [2, 2, 7], [3]],)
Expected Output: [1, 2, 2, 3, 4, 7, 9]
Explanation: Source Example 1: three arrays interleave and the duplicate 2 is kept.
Input: ([[], [-5, 0], [], [-5, 10]],)
Expected Output: [-5, -5, 0, 10]
Explanation: Source Example 2: empty arrays contribute nothing and the duplicate -5 is kept.
Hints
- The source names the two-pointer method: start with the smaller problem of combining just two sorted arrays into one sorted array in a single pass.
- The source also names divide and conquer: think about how to repeatedly reduce the number of arrays until only one remains.
- Empty inner arrays and an empty outer list are valid inputs, and every duplicate must survive into the output.