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
- 1 ≤ k ≤ 10^4
- 1 ≤ m
- total elements ≤ 10^5
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
- The next output element is the smallest among the current heads of the k arrays.
- 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);
}
}