[InterviewBit] Merge K sorted arrays!

Merge K sorted arrays!

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> Solution::solve(vector<vector<int> > &A) {
priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> q;
for(int i = 0; i < A.size(); i++) q.push({A[i][0], i, 0});
vector<int> res;
while(q.size()) {
auto [v,r,c] = q.top(); q.pop();
res.push_back(v);
if(A[r].size() != c + 1) q.push({A[r][c+1],r,c+1});
}

return res;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/11/07/PS/interviewbit/merge-k-sorted-arrays/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.