Smallest Range Covering Elements from K Lists
Problem
Given k sorted lists, find the smallest range [a, b] that includes at least one number from each list.
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]][20, 24]def smallest_range(nums):
import heapq
h = [(row[0], i, 0) for i, row in enumerate(nums)]
heapq.heapify(h)
hi = max(r[0] for r in nums); best = [-10**9, 10**9]
while True:
lo, i, j = heapq.heappop(h)
if hi - lo < best[1] - best[0]: best = [lo, hi]
if j + 1 == len(nums[i]): return best
nxt = nums[i][j+1]; hi = max(hi, nxt)
heapq.heappush(h, (nxt, i, j+1))function smallestRange(nums) {
const h = nums.map((r, i) => [r[0], i, 0]);
h.sort((a, b) => a[0] - b[0]);
let hi = Math.max(...nums.map(r => r[0])); let best = [-1e9, 1e9];
while (true) {
const [lo, i, j] = h.shift();
if (hi - lo < best[1] - best[0]) best = [lo, hi];
if (j + 1 === nums[i].length) return best;
const nxt = nums[i][j+1]; hi = Math.max(hi, nxt);
let k = 0; while (k < h.length && h[k][0] < nxt) k++;
h.splice(k, 0, [nxt, i, j+1]);
}
}int[] smallestRange(List> nums) {
PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int hi = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) { pq.offer(new int[]{ nums.get(i).get(0), i, 0 }); hi = Math.max(hi, nums.get(i).get(0)); }
int[] best = new int[]{ -100000, 100000 };
while (true) {
int[] t = pq.poll(); int lo = t[0], i = t[1], j = t[2];
if (hi - lo < best[1] - best[0]) best = new int[]{ lo, hi };
if (j + 1 == nums.get(i).size()) return best;
int nxt = nums.get(i).get(j+1); hi = Math.max(hi, nxt);
pq.offer(new int[]{ nxt, i, j+1 });
}
} vector smallestRange(vector>& nums) {
priority_queue, vector>, greater<>> pq;
int hi = INT_MIN;
for (int i = 0; i < (int)nums.size(); i++) { pq.push({nums[i][0], i, 0}); hi = max(hi, nums[i][0]); }
vector best = {-100000, 100000};
while (true) {
auto [lo, i, j] = pq.top(); pq.pop();
if (hi - lo < best[1] - best[0]) best = {lo, hi};
if (j + 1 == (int)nums[i].size()) return best;
int nxt = nums[i][j+1]; hi = max(hi, nxt);
pq.push({nxt, i, j+1});
}
} Explanation
A valid range must touch every list, so at any moment we look at one chosen number per list. The range covering them is simply [min, max] of those chosen numbers. We use a min-heap to always know the smallest, and a separate variable hi to track the largest.
We seed the heap with the first element of each (sorted) list, recording which list and index each came from. The current range is from the heap's top (the min) up to hi.
To try to shrink the range, the only useful move is to raise the minimum. So we pop the smallest element and advance to the next number in its list. That new number might become the new hi, and the heap gives us a new min. After each move we check if the current range is the best so far.
We stop the moment a list runs out: once the popped element was the last in its list, we can never again include that list, so no smaller valid range is possible and we return the best found.
Example: with lists like [4,10,15,24,26], [0,9,12,20], [5,18,22,30], advancing the smallest each time eventually lands on 24, 20, 22, giving the tight range [20, 24].