Merge K sorted arrays

1 min read

https://practice.geeksforgeeks.org/problems/merge-k-sorted-arrays/1

class Solution {
public:
  vector<int> mergeKArrays(vector<vector<int>> arr, int k) {
    vector<int> res;
    vector<int> ptrs(k, 0);

    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        hp;

    for (int i = 0; i < k; i++) {
      hp.push({arr[i][0], i});
    }

    for (int i = 0; i < k * k; i++) {
      pair<int, int> tmp = hp.top();
      hp.pop();
      ptrs[tmp.second]++;

      if (ptrs[tmp.second] < k) {
        hp.push({arr[tmp.second][ptrs[tmp.second]], tmp.second});
      } else {
        hp.push({INT_MAX, tmp.second});
      }

      res.push_back(tmp.first);
    }
    return res;
  }
};
Kth largest element in an array
Merge 2 binary max heaps