Merge Multiple Sorted Arrays
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's competency in array manipulation, merging techniques, and algorithmic complexity analysis, including handling edge cases like empty inputs and preserving duplicate values.
Constraints
- 0 <= n <= 10^4, where n is the number of arrays
- 0 <= total number of elements across all arrays <= 2 * 10^5
- Each inner array is sorted in nondecreasing order; values may be negative and duplicates are allowed
Examples
Input: ([[1, 4, 7], [1, 3, 5], [2, 6]],)
Expected Output: [1, 1, 2, 3, 4, 5, 6, 7]
Explanation: Merging the three sorted arrays while preserving duplicates gives one fully sorted result.
Input: ([],)
Expected Output: []
Explanation: There are no arrays to merge, so the result is empty.
Input: ([[], [2, 2, 2], [], [1], [3, 4]],)
Expected Output: [1, 2, 2, 2, 3, 4]
Explanation: Empty arrays contribute nothing, and duplicate 2s are preserved.
Input: ([[-5, -1, 3], [-2, -2, 4], [0], []],)
Expected Output: [-5, -2, -2, -1, 0, 3, 4]
Explanation: Negative values, duplicates, and an empty array are all handled correctly.
Input: ([[], [], []],)
Expected Output: []
Explanation: All arrays are empty, so the merged output is also empty.
Hints
- You only need to track the smallest unmerged element from each array at any time.
- A min-heap is useful for repeatedly selecting the next smallest value among multiple sorted arrays.