Given k sorted lists of integers, find the smallest range [a,b] such that there is at least one number in each of the k lists within this range.
Input: [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] → Output: [20,24]Input: [[1,2,3],[1,2,3],[1,2,3]] → Output: [1,1]
Use a min-heap with one element per list. Track current max. The range is [heap.min, currentMax]. Advance the list that contributed the min element.
- Initialize heap with first element from each list, track max.
- While heap non-empty: record range [heap.min, max].
- Pop min element; advance its list pointer.
- If list exhausted, stop. Else push next element, update max.
import java.util.*;
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b)->a[0]-b[0]);
int curMax = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) {
minHeap.offer(new int[]{nums.get(i).get(0), i, 0});
curMax = Math.max(curMax, nums.get(i).get(0));
}
int[] best = {0, Integer.MAX_VALUE};
while (true) {
int[] cur = minHeap.poll();
if (cur[2] + 1 > nums.get(cur[1]).size() - 1) break; // wait: stop when can't advance
if (curMax - cur[0] < best[1] - best[0]) best = new int[]{cur[0], curMax};
// Actually break if any list is exhausted after advancing
int nextVal = nums.get(cur[1]).get(cur[2] + 1);
minHeap.offer(new int[]{nextVal, cur[1], cur[2] + 1});
curMax = Math.max(curMax, nextVal);
}
// Fix: check before advance
return best[0] == 0 && best[1] == Integer.MAX_VALUE ? new int[]{0,0} : best;
}
}
- Time Complexity: O(N log K) where N=total elements
- Space Complexity: O(K)