Smallest Range Covering Elements from K Lists

Share

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.

Example 1
Input: [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] → Output: [20,24]
Example 2
Input: [[1,2,3],[1,2,3],[1,2,3]] → Output: [1,1]

Solution Approach

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.
Java
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)