Return the K Smallest Values from Sorted Arrays
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Return the K Smallest Values from Sorted Arrays
### Problem
Implement `kSmallestFromSortedArrays(arrays, takeCount) -> values`.
Each inner array is sorted in nondecreasing order. Return exactly the `takeCount` smallest values across all arrays, including duplicates, in nondecreasing order. Do not place every input value into one heap; the algorithm must exploit the ordering inside each array and keep only its current frontier available for selection.
### Portable Contract
- `arrays` is a JSON array of integer arrays. Inner arrays may be empty.
- Every inner array is sorted in nondecreasing order.
- Let `N` be the total number of values across all inner arrays. `0 <= N <= 16,000` and `0 <= takeCount <= N`.
- Every value is between `-1,000,000,000` and `1,000,000,000`, so ordinary 32-bit signed integers are sufficient.
- Equal values from the same or different arrays are separate elements and must be preserved.
- When `takeCount == 0`, return an empty array.
- Do not modify `arrays`.
- Let `B` be the compact UTF-8 JSON byte length of `[arrays,takeCount]`, counting every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned integer array. Inputs guarantee `R <= 96,000`, so the serialized input and result together are at most `192,000` bytes.
- For `m = arrays.length` and `r = takeCount`, target `O(m + r log m)` time and `O(m)` auxiliary space, excluding the returned array.
The contract projects directly to all four languages: `list[list[int]]` plus `int` returning `list[int]` in Python, nested arrays plus a number in JavaScript, `List<List<Integer>>` plus `int` returning `List<Integer>` in Java, and `vector<vector<int>>` plus `int` returning `vector<int>` in C++.
```hint Keep one candidate per nonempty source
At any moment, values after the first unconsumed value of one sorted array cannot be the next global minimum.
```
```hint Preserve multiplicity
Two equal frontier values represent two different elements even though their numeric values compare equal.
```
### Examples
```text
arrays = [[1, 4, 7], [2, 2, 9], [], [3, 8]]
takeCount = 5
values = [1, 2, 2, 3, 4]
```
```text
arrays = [[-5, -1], [0], [3, 3]]
takeCount = 0
values = []
```
### Discussion Requirements
- Explain what each frontier entry identifies and how the next value from that same array becomes eligible.
- State why the heap size depends on the number of arrays rather than the total number of values.
- Cover empty arrays, repeated values, `takeCount == 0`, and `takeCount == N`.
- Compare the frontier method with flattening and sorting all values or inserting every value into one heap.
Quick Answer: Return the requested number of smallest values across multiple sorted arrays while preserving duplicates. The question evaluates frontier-based merging, empty-source handling, output ordering, and complexity that depends on the number of arrays rather than all input values.
Implement `kSmallestFromSortedArrays(arrays, takeCount) -> values`.
`arrays` is a list of integer arrays, and every inner array is already sorted in
nondecreasing order. Inner arrays may be empty. Return exactly the `takeCount`
smallest values across all arrays, including duplicates, in nondecreasing order.
Equal values coming from the same array or from different arrays are separate
elements: every one of them must be preserved. When `takeCount == 0`, return an
empty array. `arrays` must not be modified.
The intended solution does not put every value into one heap and does not flatten
and sort everything. It exploits the ordering already present inside each array
and keeps only the current frontier - the first unconsumed value of each array -
available for selection, so the auxiliary structure is sized by the number of
arrays rather than by the total number of values.
Output semantics
- The result is a list of values, never indices or pairs.
- Its length is exactly `takeCount`.
- It is sorted in nondecreasing order, so the returned sequence is unique even
when equal values could have come from different arrays.
Example 1
```
arrays = [[1, 4, 7], [2, 2, 9], [], [3, 8]]
takeCount = 5
values = [1, 2, 2, 3, 4]
```
The five smallest values across all arrays are 1, 2, 2, 3 and 4. The empty inner
array contributes nothing, and both copies of 2 from the second array are kept.
Example 2
```
arrays = [[-5, -1], [0], [3, 3]]
takeCount = 0
values = []
```
`takeCount == 0`, so nothing is selected even though the input is nonempty.
Constraints
- arrays is a list of integer arrays; inner arrays may be empty
- every inner array is sorted in nondecreasing order
- 0 <= N <= 16,000, where N is the total number of values across all inner arrays
- 0 <= takeCount <= N
- -1,000,000,000 <= value <= 1,000,000,000 for every value, so ordinary 32-bit signed integers are sufficient (no intermediate quantity is summed or scaled)
- B <= 96,000, where B is the compact UTF-8 JSON byte length of [arrays, takeCount]
- R <= 96,000, where R is the compact UTF-8 JSON byte length of the returned integer array, so the serialized input and result together are at most 192,000 bytes
- arrays must not be modified
- target O(m + r log m) time and O(m) auxiliary space excluding the returned array, for m = number of arrays and r = takeCount
Examples
Input: ([[1, 4, 7], [2, 2, 9], [], [3, 8]], 5)
Expected Output: [1, 2, 2, 3, 4]
Input: ([[-5, -1], [0], [3, 3]], 0)
Expected Output: []
Hints
- At any moment, values that sit after the first unconsumed value of one sorted array cannot be the next global minimum.
- Two equal frontier values represent two different elements even though their numeric values compare equal - decide what an entry must identify so the next value from that same array can become eligible.
- Ask what the auxiliary structure must hold for its size to depend on the number of arrays rather than on the total number of values.