Merge multiple sorted arrays using min-heap

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.)

Merge multiple sorted arrays using min-heap

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.

Hints

1. Use a min-heap (priority queue) that holds the current smallest unconsumed element of each non-empty array.
2. Store tuples of (value, array_index, element_index) so that after popping the minimum you know which array to advance.
3. 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.
4. This yields O(N log k) — strictly better than the O(N*k) repeated-linear-scan approach when k is large.