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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question