Smallest Range Covering Elements from K Lists

Share

Find smallest range [a,b] that includes at least one element from each of K sorted lists.

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

Solution Approach

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