Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Merge K Sorted Arrays

Medium · Heap & Priority Queue · Asked at Amazon, Google, Microsoft, Meta, Uber

Merge k sorted arrays into one sorted array.

Input

First line: k. Next k lines: an array each — first its length m, then m sorted integers.

Output

All elements in sorted order, space-separated.

Constraints

Min-heap of (value, array index, position). Pop the smallest, output it, push the next element of the same array. O(N log k).

Example 1

Input

3
3 1 4 5
3 1 3 4
2 2 6

Output

1 1 2 3 4 4 5 6

Example 2

Input

1
2 -1 0

Output

-1 0

Hints

  1. The next output element is the smallest among the current heads of the k arrays.
  2. Keep those heads in a min-heap of (value, array, index). Pop the minimum, output it, and push the next element from the same array.

Approach

Initialise the heap with the first element of every array. Repeatedly pop (v, i, j), append v, and if array i has an element at j + 1, push it. The heap never holds more than k entries, so each of the N total elements costs O(log k).

Complexity: O(N log k) time · O(k) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    cin >> k;
    vector<vector<long long>> arr(k);
    for (auto &a : arr) {
        int m;
        cin >> m;
        a.resize(m);
        for (auto &x : a) cin >> x;
    }
    typedef tuple<long long, int, int> T;
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < k; i++) pq.emplace(arr[i][0], i, 0);
    vector<long long> out;
    while (!pq.empty()) {
        long long v;
        int i, j;
        tie(v, i, j) = pq.top();
        pq.pop();
        out.push_back(v);
        if (j + 1 < (int)arr[i].size()) pq.emplace(arr[i][j + 1], i, j + 1);
    }
    for (size_t i = 0; i < out.size(); i++) cout << out[i] << (i + 1 < out.size() ? " " : "\n");
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
k, p, arr = data[0], 1, []
for _ in range(k):
    m = data[p]
    arr.append(data[p + 1 : p + 1 + m])
    p += 1 + m
heap = [(a[0], i, 0) for i, a in enumerate(arr)]
heapq.heapify(heap)
out = []
while heap:
    v, i, j = heapq.heappop(heap)
    out.append(v)
    if j + 1 < len(arr[i]):
        heapq.heappush(heap, (arr[i][j + 1], i, j + 1))
print(*out)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int k = (int) in.nval;
        long[][] arr = new long[k][];
        for (int i = 0; i < k; i++) {
            in.nextToken();
            int m = (int) in.nval;
            arr[i] = new long[m];
            for (int j = 0; j < m; j++) {
                in.nextToken();
                arr[i][j] = (long) in.nval;
            }
        }
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        for (int i = 0; i < k; i++) pq.add(new long[] {arr[i][0], i, 0});
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            sb.append(first ? "" : " ").append(t[0]);
            first = false;
            int i = (int) t[1], j = (int) t[2];
            if (j + 1 < arr[i].length) pq.add(new long[] {arr[i][j + 1], i, j + 1});
        }
        System.out.println(sb);
    }
}

Solve Merge K Sorted Arrays online · All practice problems