Find smallest range [a,b] that includes at least one element from each of K sorted lists.
Input: nums=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] → Output: [20,24]
Input: nums=[[1,2,3],[1,2,3],[1,2,3]] → Output: [1,1]
Use a min-heap containing one element from each list. Track current max. Advance the minimum element.
- Add first element of each list to min-heap, track global max
- While heap is full (all lists represented)
- Current range = [heap.min, globalMax]
- Poll min, advance to next in its list
- Update globalMax as needed
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->nums.get(a[0]).get(a[1])-nums.get(b[0]).get(b[1]));
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.size(); i++) {
pq.offer(new int[]{i, 0});
max = Math.max(max, nums.get(i).get(0));
}
int[] res = {0, Integer.MAX_VALUE};
while (pq.size() == nums.size()) {
int[] cur = pq.poll();
int min = nums.get(cur[0]).get(cur[1]);
if (max - min < res[1] - res[0]) res = new int[]{min, max};
if (cur[1] + 1 < nums.get(cur[0]).size()) {
cur[1]++;
pq.offer(cur);
max = Math.max(max, nums.get(cur[0]).get(cur[1]));
}
}
return res;
}
- Time Complexity: O(n log k)
- Space Complexity: O(k)