Skip to main content

Merge K Sorted Arrays

Problem​

You have been given ‘K’ different arrays/lists, which are sorted individually (in ascending order). You need to merge all the given arrays/list such that the output array/list should be sorted in ascending order.

Solution Approach​

Expected Time complexity: O(n∗log(n))O(n*log(n))

Click - to see solution code
vector<int> mergeKSortedArrays(vector<vector<int>>& kArrays, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (auto x : kArrays) {
        for (auto y : x) minHeap.push(y);
    }
    vector<int> res;

    while (!minHeap.empty()) {
        res.push_back(minHeap.top());
        minHeap.pop();
    }

    return res;
}