Merge K Sorted Arrays

HardHeapmin-heap merge

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of k arrays, where each individual array is already sorted in non-decreasing order. The arrays may have different lengths, and some of them may be empty. Combine every element from all of the arrays into a single array that is also sorted in non-decreasing order, and return it. Duplicate values are allowed and must all be preserved in the output. If every input array is empty (or the list of arrays itself is empty), return an empty array. Aim for a solution that is efficient even when there are many arrays. A min-heap that tracks the current smallest unconsumed element across all arrays lets you produce the merged result in O(N log k) time, where N is the total number of elements and k is the number of arrays.

Examples

Input: arrays = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
All eight values from the three arrays are interleaved into one sorted sequence. The duplicate `1` and duplicate `4` are both kept.
Input: arrays = [[10,20,30],[5,15,25],[1,2,3]]
Output: [1,2,3,5,10,15,20,25,30]
The smallest available element is repeatedly chosen, draining the third array first, then weaving in the others.
Input: arrays = [[],[],[]]
Output: []
Every input array is empty, so there is nothing to merge.

Constraints

  • `0 <= k <= 10^4` (k is the number of arrays)
  • `0 <= arrays[i].length`
  • The total number of elements across all arrays does not exceed `10^5`
  • `-10^9 <= arrays[i][j] <= 10^9`
  • Each `arrays[i]` is sorted in non-decreasing order

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.