Skip to main content
Ace Hired
All coding problems

Merge K Sorted Arrays

HardheapsK-way merge with a min-heap (priority queue)heappriority-queuemerge

Maintained by Vikas D, software engineer

You are given a list of arrays, where each inner array is itself sorted in non-decreasing order. Your job is to fold all of these inputs together into one array that is also sorted in non-decreasing order and holds every value from every input.

Duplicates are kept, not removed. If the same number appears in three different arrays, it appears three times in the result. Values can be negative, and the inputs can vary widely in length.

The key signal is that each input is pre-sorted. A naive approach ignores that and just sorts everything from scratch, but the better solutions exploit the existing order so you never re-compare elements that are already known to be in sequence.

Examples

Input: arrays = [[1,4,7],[2,5,8],[3,6,9]]
Output: [1,2,3,4,5,6,7,8,9]

The three arrays interleave perfectly. Repeatedly taking the smallest available front element gives 1 from the first, 2 from the second, 3 from the third, and so on.

Input: arrays = [[1,2,3],[4,5]]
Output: [1,2,3,4,5]

These two ranges do not overlap. The first array is fully drained before any element of the second is smaller than what remains, so they simply concatenate in order.

Input: arrays = [[-5,-1,0],[0,3,7],[2,4]]
Output: [-5,-1,0,0,2,3,4,7]

Negatives sort ahead of positives, and the shared value 0 appears in two arrays so it shows up twice in the merged output.

Constraints

  • 1 <= k <= 1000 (k is the number of arrays)
  • 1 <= arrays[i].length <= 500
  • -10^4 <= arrays[i][j] <= 10^4
  • Each arrays[i] is sorted in non-decreasing order
  • Total element count N is at most k * 500

Visible test cases

  • mergeKSortedArrays([[1,4,7],[2,5,8],[3,6,9]]) == [1,2,3,4,5,6,7,8,9]
  • mergeKSortedArrays([[1,2,3],[4,5]]) == [1,2,3,4,5]
  • mergeKSortedArrays([[1]]) == [1]
  • mergeKSortedArrays([[-5,-1,0],[0,3,7],[2,4]]) == [-5,-1,0,0,2,3,4,7]
  • mergeKSortedArrays([[1,1,1],[1,1]]) == [1,1,1,1,1]

Hints

Hint 1

At any moment, the next value in the merged output is the smallest among the current front elements of the arrays that still have elements left. You never need to look past the front of each array.

Hint 2

You want a structure that hands you the minimum of up to k candidates quickly and lets you replace that minimum with the next element from the same array. A min-heap does exactly this in logarithmic time per operation.

Hint 3

Store a small record in the heap for each candidate: the value plus which array it came from and its position in that array. When you pop the smallest, push the next element from that same array if one exists.

Loading the editor...

Approaches

Concatenate then sort

Time O(N log N) where N is the total number of elements · Space O(N) for the combined array (or O(log N) extra beyond the output, depending on the sort)

Ignore the existing order, dump every element into one flat array, and run a general comparison sort over the whole thing.

  1. Create an empty output array.
  2. Walk every input array and append all of its elements to the output.
  3. Sort the output array in non-decreasing order.
  4. Return it.

K-way merge with a min-heap

Time O(N log k) where k is the number of arrays · Space O(k) for the heap plus O(N) for the output

Keep only the current front element of each array in a min-heap. The heap root is always the next value to emit, and after emitting it you replace it with the successor from the same array.

  1. Seed the heap with the first element of every non-empty array, tagged with its array index and element index 0.
  2. Pop the smallest record from the heap and append its value to the result.
  3. If the array it came from has another element after that position, push that next element with its updated index.
  4. Repeat until the heap is empty, then return the result.

Common mistakes

  • Pushing a whole array's elements into the heap at once instead of one front element at a time. That makes the heap hold N items and degrades the bound to O(N log N), throwing away the advantage over plain sorting.
  • Comparing heap records by the tuple instead of by value alone in a language where tuple comparison falls through to the array index. Make sure ties break on something stable so the comparison never errors or reorders incorrectly.
  • Forgetting that values can be negative, so any sentinel or default-zero assumption about the smallest possible element is wrong.
  • Dropping duplicates. The result must keep every occurrence, so do not use a set or a dedup step.
  • Off-by-one when advancing within an array: push the element at index i+1 only when i+1 is still in bounds.

Follow-up variations

  • What changes if the inputs are singly linked lists instead of arrays, so you cannot index into them directly?
  • How would you adapt this to merge a stream of sorted arrays that arrive over time and may not all fit in memory at once?
  • If k is very large but each array is tiny, does the heap approach still beat concatenate-and-sort, and where is the crossover?
  • Can you produce the result lazily, yielding one element at a time, so a caller can stop early after reading the first m values?

Recommended problems

Build the rest of your prep