Merge K sorted (K-way Merge Sub-pattern)
Produce the full merged order. The heap holds one front per list; pop the smallest, write it out, push its successor.
- ›
"merge k sorted arrays / lists"
- ›
"each element is at most k positions away from its sorted position"
- ›
"the nth number whose only prime factors are 2, 3, 5"
Merge K Sorted Arrays is the template: store (value, array, index). Merge k Sorted Lists stores the node itself, since node->next is the successor. Skip empty lists so you never push a null. Nearly Sorted is the same idea on one array: the smallest remaining item must be within the next k + 1 cells, so a heap of size k + 1 slides along. Ugly Number II merges three sorted streams that it builds as it goes (ugly·2, ugly·3, ugly·5). With only three streams, three pointers replace the heap, and every pointer that ties advances, so 6 isn't written twice.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Merge K Sorted ArraysWalkthroughMediumBasic Anchor·GeeksforGeeks
- 2Merge k Sorted ListsWalkthroughHardBasic Reinforcement·LeetCode #23
- 3Sort a Nearly Sorted (K-sorted) ArrayWalkthroughMediumSlight Variation·GeeksforGeeks
- 4Ugly Number IIWalkthroughMediumPattern Transfer·LeetCode #264
Template
// Merge K sorted arrays: the heap holds one front per array.
vector<int> mergeKArrays(vector<vector<int>>& arrs) {
// (value, array, index); greater<> turns priority_queue into a min-heap
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
for (int a = 0; a < (int)arrs.size(); a++)
if (!arrs[a].empty()) pq.push({arrs[a][0], a, 0}); // skip empty arrays
vector<int> out;
while (!pq.empty()) {
auto [v, a, i] = pq.top(); pq.pop(); // smallest front overall
out.push_back(v);
if (i + 1 < (int)arrs[a].size())
pq.push({arrs[a][i + 1], a, i + 1}); // its successor takes its place
}
return out;
}