Merge K Sorted Arrays Without Duplicates
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `merge_sorted_unique(sorted_arrays)`.
Each input array is sorted in ascending order. Merge all arrays into one ascending array containing each value exactly once. Empty arrays and values repeated within or across arrays must be handled correctly.
Let `N` be the total number of input elements and `k` the number of arrays. Target `O(N log k)` time and `O(k)` auxiliary space, excluding the returned array.
```hint Keep one frontier value per array
Put the first value from every nonempty array into a min-heap together with its array and position.
```
```hint Deduplicate at the output boundary
After removing the next smallest value, append it only when it differs from the last emitted value, then advance within the same source array.
```
### Discussion Extensions
- For exactly three arrays, compare a three-pointer implementation with the heap-based general solution.
- How would the algorithm change if the inputs were streams rather than materialized arrays?
Quick Answer: Merge k sorted arrays into one ascending list with duplicate values removed. Use a min-heap for O(N log k) time and O(k) extra space, with correct handling of empty arrays and repeated values.
Merge k ascending integer arrays into one ascending list that contains each value exactly once. Handle empty arrays and duplicates both within one array and across arrays.
Constraints
- 0 <= sorted_arrays.length <= 100.
- The total number of input values N is at most 5,000.
- Each inner array is sorted in nondecreasing order.
- Every value is an integer in the inclusive range [-10^12, 10^12].
Examples
Input: ([],)
Expected Output: []
Explanation: No arrays produce an empty result.
Input: ([[]],)
Expected Output: []
Explanation: An explicitly empty source contributes no values.
Hints
- Keep only the next unconsumed value from each nonempty array in a shared frontier.
- Deduplicate when emitting the globally smallest frontier value rather than modifying every input array first.