Merge K sorted arrays

Practice Link

Given k sorted arrays arranged in the form of a matrix of size k * k. The task is to merge them into one sorted array.

Return the merged sorted array

Naive Approach#

Concatenate all k arrays into one big array and sort it. Simple and correct, but discards the sorted-order information already present in each array, paying O(n log n) to re-sort what was already partially organized.

• Combine all k sorted arrays → O(n)
• Sort the combined array → O(n log n), where n is the total number of elements across all k arrays.

Using Min Heap#

Since each array is already sorted, the globally smallest unprocessed element must be among the current heads of the k arrays. A min-heap tracks these k candidates efficiently — the top of the heap is always the next element to output. After extracting a minimum, we advance the pointer in that element's source array and push the next element into the heap. This leverages existing sorted order and brings each of the n insertions/extractions down to O(log k).

This approach works for arrays of different or equal sizes.

• Use a min-heap to store the current smallest elements from each array.
• Each entry in the heap is of the form {value, {array_index, element_index}}.
• Initially push the first element of each array into the heap.
• Repeatedly:
  • Pop the smallest element, add it to the result.
  • Push the next element from the same array (if any) into the heap.

typedef pair<int,pair<int,int>> ppi;
class Solution {
  public:
    // Function to merge k sorted arrays.
    vector<int> mergeKArrays(vector<vector<int>> arr, int K) {
        priority_queue<ppi, vector<ppi>, greater<ppi>> pq;
        
        //insert first element of every array
        for(int i=0;i<arr.size();i++)
            pq.push({arr[i][0], {i,0}});
            
        
        //keep picking the top element from minHeap and adding next from the same array.
        vector<int> ans;
        while(!pq.empty())
        {
            auto t = pq.top();
            pq.pop();
            
            ans.push_back(t.first);
            
            int x = t.second.first;
            int y = t.second.second;
            
            if(y+1 < arr[x].size())
                pq.push({arr[x][y+1], {x, y+1}});
        }
        return ans;
    }
};

Time Complexity: O(nlogk), each heap operation is log k and there are n elements total

Space Complexity: O(n) + O(k)