Merge multiple sorted arrays using min-heap
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
### Problem
You are given `k` sorted arrays of integers:
- `arrays[0], arrays[1], ..., arrays[k-1]`
- Each `arrays[i]` is sorted in **non-decreasing** order.
- The total number of elements across all arrays is `N`.
Your task is to merge these `k` sorted arrays into a **single sorted array** (or list) containing all `N` elements.
You should design an algorithm that is **asymptotically optimal** in terms of time complexity for large `k` and `N`. A straightforward approach that repeatedly scans all array heads at each step is too slow when `k` is large.
**Output**: a single sorted sequence of all elements from the `k` arrays.
#### Example
Input:
- `k = 3`
- `arrays[0] = [1, 4, 9]`
- `arrays[1] = [2, 6]`
- `arrays[2] = [0, 3, 7, 8]`
Output:
- `[0, 1, 2, 3, 4, 6, 7, 8, 9]`
#### Constraints
- `1 <= k <= 10^5`
- Each array length can be zero or more.
- Total number of elements `N` across all arrays: `0 <= N <= 10^6` (assume this upper bound for complexity discussion).
- Integer values fit in 32-bit signed range.
#### Requirements
1. Describe an efficient algorithm for this problem, including:
- Data structures you would use.
- Time and space complexity.
2. Then implement the function that merges the arrays following your algorithm.
*(Hint: Consider a priority-based data structure that efficiently gives you the smallest current element among the `k` arrays.)*
Quick Answer: This question evaluates algorithm design and data structure proficiency, focusing on merging multiple sorted sequences and reasoning about time and space complexity for large numbers of arrays and elements.
You are given `k` sorted arrays of integers, where each `arrays[i]` is sorted in non-decreasing order. Merge them into a single sorted list containing all `N` elements.
A naive approach that rescans every array head at each of the `N` steps costs O(N*k), which is too slow when `k` is large. Use a min-heap (priority queue) holding the current front element of each non-empty array. Repeatedly pop the smallest, append it to the output, and push the next element from the same source array. Each of the N elements is pushed and popped once, and the heap holds at most k entries, giving O(N log k) time.
Write `solution(arrays)` that takes a list of `k` sorted integer lists and returns the merged sorted list.
Example:
Input: arrays = [[1, 4, 9], [2, 6], [0, 3, 7, 8]]
Output: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Constraints:
- 1 <= k <= 10^5
- Each array length can be zero or more.
- 0 <= N <= 10^6 total elements.
- Integer values fit in 32-bit signed range.
- Some input arrays may be empty; the overall list may be empty.
Constraints
- 1 <= k <= 10^5
- 0 <= N <= 10^6 total elements across all arrays
- Each individual array length can be zero or more
- Integer values fit in 32-bit signed range
- Input arrays may be empty and the merged result may be empty
Examples
Input: ([[1, 4, 9], [2, 6], [0, 3, 7, 8]],)
Expected Output: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Explanation: The example case: three sorted arrays merged into one fully sorted list.
Input: ([],)
Expected Output: []
Explanation: No arrays at all -> empty result.
Hints
- Use a min-heap (priority queue) that holds the current smallest unconsumed element of each non-empty array.
- Store tuples of (value, array_index, element_index) so that after popping the minimum you know which array to advance.
- Initialize the heap with the first element of every non-empty array, then loop: pop the minimum, append it, and push the next element from that same array until the heap is empty.
- This yields O(N log k) — strictly better than the O(N*k) repeated-linear-scan approach when k is large.