Combine Many Sorted Integer Arrays into One Non-Decreasing Array
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a collection of integer arrays, each already sorted in non-decreasing order. Combine them into one array that contains every element of every input array, sorted in non-decreasing order.
### Function Signature
```python
def merge_sorted_arrays(lists: list[list[int]]) -> list[int]:
```
### Rules
- Keep duplicates: a value appears in the output exactly as many times as it appears across all input arrays combined.
- The output is in non-decreasing order, so the answer is unique.
- `lists` may be empty, and any input array may be empty. If there are no elements at all, return `[]`.
- The input arrays may have different lengths.
### Constraints
- `0 <= len(lists) <= 10^4`
- `0 <= len(lists[i]) <= 500`
- The total number of elements across all arrays is at most `10^4`.
- `-10^4 <= lists[i][j] <= 10^4`
- Each `lists[i]` is sorted in non-decreasing order.
### Examples
**Example 1**
```text
Input: lists = [[2, 5, 9], [1, 5], [3, 8, 10]]
Output: [1, 2, 3, 5, 5, 8, 9, 10]
```
Both copies of 5 are kept.
**Example 2**
```text
Input: lists = []
Output: []
```
**Example 3**
```text
Input: lists = [[], [-3, -3, 0], [-5]]
Output: [-5, -3, -3, 0]
```
The empty array contributes nothing; the other two are interleaved.
Overview: A coding question asking you to merge many integer arrays, each already sorted in non-decreasing order, into a single sorted array that keeps every duplicate value. It tests multi-way merging, efficiency as the number of input arrays grows, and edge cases such as empty inputs and arrays of different lengths.
Read the full Meta Software Engineer interview experience this question came from