2Brute2Best
🔥0
03

Smallest range (K-way Merge Sub-pattern)

Keep exactly one item from every list in the heap, track the largest of them, and repeatedly replace the smallest.

Signals in the problem statement
  • ›

    "smallest range that includes at least one number from each of the k lists"

  • ›

    "pick one item from each group so that max − min is as small as possible"

What makes it different

Unlike the other two, the heap is never allowed to lose a list: it always holds exactly K items, one per list. The answer is read at every step, not at the end. The loop stops the moment any list runs out, because then no range can cover every list. A sliding window over all items sorted together also works (O(N log N)); the heap version is O(N log K).

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Smallest Range Covering Elements from K Lists
    Interview-Level·LeetCode #632
    Hard

Template

smallest-range-template.cpp
// Smallest range [lo, hi] containing at least one number from each sorted list.
vector<int> smallestRange(vector<vector<int>>& nums) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;  // (value, list, index)
    int curMax = INT_MIN;
    for (int l = 0; l < (int)nums.size(); l++) {
        pq.push({nums[l][0], l, 0});                        // exactly one item per list
        curMax = max(curMax, nums[l][0]);
    }
    vector<int> best = {get<0>(pq.top()), curMax};
    while (true) {
        auto [v, l, i] = pq.top(); pq.pop();                // [v, curMax] covers every list
        if ((long long)curMax - v < (long long)best[1] - best[0]) best = {v, curMax};
        if (i + 1 == (int)nums[l].size()) break;            // list l ran out: no more full ranges
        pq.push({nums[l][i + 1], l, i + 1});
        curMax = max(curMax, nums[l][i + 1]);               // the new item may be the new max
    }
    return best;
}
Remember this · K-way Merge
Trigger
K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.
Think
The next smallest item overall must be the front of some list — which one?
Key question
What do I push back into the heap after popping?
Kth smallest across lists