Opening the reading…
Opening the reading…
LINKED LIST › LINKED LIST (PART 1)
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →At any moment, the smallest value not yet placed in the answer must be the first unused value of some row. Every later value in that same row is at least as large, so it cannot be the next answer while that row's front value is still waiting. This reduces the whole problem to choosing the smallest among the current front values.
A min-heap stores one candidate from each non-empty row. Remove the smallest candidate, append it to the result, and replace it with the next value from that same row. The heap never needs to store every remaining value: values behind a row's front are already ordered and can wait until their predecessor is removed.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(N log k) | Each of the N values enters the heap at most once and leaves it exactly once. Each heap operation compares along at most log k levels, so the total work is bounded by a constant number of heap operations per value times log k. |
| Space | O(k) extra, excluding the output | The heap stores at most one candidate per row, and the row and position fields use constant space per candidate. The returned array is required output and is excluded; the auxiliary bound is O(k) even when the total input has N values. |
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> flattenSortedLists(vector<vector<int>> lists) {
struct Item {
int value;
int row;
int index;
};
struct Compare {
bool operator()(const Item& a, const Item& b) const {
return a.value > b.value;
}
};
priority_queue<Item, vector<Item>, Compare> heap;
int total = 0;
for (int row = 0; row < static_cast<int>(lists.size()); ++row) {
total += static_cast<int>(lists[row].size());
if (!lists[row].empty()) {
heap.push({lists[row][0], row, 0});
}
}
vector<int> answer;
answer.reserve(total);
while (!heap.empty()) {
Item current = heap.top();
heap.pop();
answer.push_back(current.value);
int nextIndex = current.index + 1;
if (nextIndex < static_cast<int>(lists[current.row].size())) {
heap.push({lists[current.row][nextIndex], current.row, nextIndex});
}
}
return answer;
}
};The comparator reverses the usual priority_queue ordering: returning a.value > b.value makes the smallest value appear at heap.top(). The row and index travel with the value, so after removal the code can advance the correct row without searching for the candidate again.
You can also merge rows in pairs: merge adjacent rows into larger sorted lists, then merge those results again until one list remains. A balanced merge tree gives O(N log k) time because each value participates in at most log k pairwise merges. This is not a strict optimisation; it replaces heap bookkeeping with temporary merged arrays and is useful when a reusable two-list merge is already available.
#include <vector>
using namespace std;
class Solution {
vector<int> mergeTwo(const vector<int>& a, const vector<int>& b) {
vector<int> merged;
merged.reserve(a.size() + b.size());
int i = 0;
int j = 0;
while (i < static_cast<int>(a.size()) && j < static_cast<int>(b.size())) {
if (a[i] <= b[j]) {
merged.push_back(a[i++]);
} else {
merged.push_back(b[j++]);
}
}
while (i < static_cast<int>(a.size())) {
merged.push_back(a[i++]);
}
while (j < static_cast<int>(b.size())) {
merged.push_back(b[j++]);
}
return merged;
}
public:
vector<int> flattenSortedLists(vector<vector<int>> lists) {
if (lists.empty()) {
return {};
}
while (lists.size() > 1) {
vector<vector<int>> nextRound;
nextRound.reserve((lists.size() + 1) / 2);
for (int i = 0; i < static_cast<int>(lists.size()); i += 2) {
if (i + 1 == static_cast<int>(lists.size())) {
nextRound.push_back(lists[i]);
} else {
nextRound.push_back(mergeTwo(lists[i], lists[i + 1]));
}
}
lists.swap(nextRound);
}
return lists[0];
}
};