Coding

Merge K Sorted Arrays

Asked atCCleartrip

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given k sorted arrays, each of size k. Merge all the arrays into one sorted array and return it.

You should use an efficient algorithm with O(k² log k) time complexity.

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

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

**Input: **k = 1, arr = [[10]]

1 <= k <= 100
Each row arr[i] is sorted in ascending order
Total elements = k × k (i.e., the matrix is k x k)

cpp

class Solution {
public:
    vector<int> mergeKSortedArrays(vector<vector<int>>& arr, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public List<Integer> mergeKSortedArrays(int[][] arr, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def mergeKSortedArrays(self, arr, k):
        # Your code goes here

javascript

class Solution {
    mergeKSortedArrays(arr, k) {
        // Your code goes here
    }
}

csharp

class Solution {
    public List<int> MergeKSortedArrays(int[][] arr, int k) {
        // Your code goes here
    }
}

func mergeKSortedArrays(arr [][]int, k int) []int {

Stuck? Show a way to structure it+

01Push the first element of each non-empty array into a min-heap.
02Pop the smallest item into the answer.
03Push its successor from the same array.
04Repeat until the heap is empty.
05Store value, array index, and element index.

Reference answer

Use a min-heap whose entries hold (value, arrayIndex, elementIndex). Seed it with the first value from every non-empty array. Repeatedly pop the smallest entry, append its value to the output, and if that source array has a successor, push the successor. The heap contains exactly the next unconsumed candidate from each array, so popping it is globally safe and preserves sorted order. This avoids repeatedly merging arrays, which can become quadratic. If there are K arrays and N total elements, every element is pushed and popped once for O(N log K) time; the heap needs O(K) space besides the output. Mention careful handling of empty arrays and duplicate values.

Then expect these follow-ups

How would you merge linked lists instead?
Tests: data-structure transfer
When is divide-and-conquer merging attractive?
Tests: tradeoffs

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question