Smallest Range Covering K Lists

How It Works

Smallest range covering K lists keeps one active element per list — a window that always touches every list. Seed a min-heap with the first element of each list, and track the maximum among the seeded values. The current candidate range is [heap top, current max]. To try to shrink it, the only legal move is to advance the list owning the minimum: pop the heap top, push that list's next element, and update the max if needed. Record the tightest range seen; stop when any list is exhausted, since no valid range can exclude a list.

The greedy step is provably safe: widening any other list's contribution cannot reduce a range whose lower bound is the minimum. Each element enters the heap once, so with n total elements the runtime is O(n log K) and space is O(K) — the same frontier idea as merging K lists, aimed at ranges instead of output order.

Step-by-Step Visualization

Code

static int[] smallestRange(List<List<Integer>> lists) {
  // Heap contains [value, listIndex, elementIndex]
  int curMax = Integer.MIN_VALUE;
  PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

  for (int i = 0; i < lists.size(); i++) {
    heap.add(new int[]{lists.get(i).get(0), i, 0});
    curMax = Math.max(curMax, lists.get(i).get(0));
  }

  int[] range = {Integer.MIN_VALUE, Integer.MAX_VALUE};
  // Pop min, check range [min, curMax], push next from same list
  // Continue until a list is exhausted
  return range;
}

Tips & Gotchas

Practice Problems

• 1Smallest Range Covering Elements from K Lists
• 2Minimize the Maximum Difference of Pairs
• 3Kth Smallest Element in a Sorted Matrix

About the K-Way Merge Pattern

Merge K sorted lists into one sorted output. Use a min-heap to always know which list has the smallest current element. Pop the smallest, add it to the result, and push the next element from that list.

Common Heap Interview Problems

• Kth Largest Element
• Top K Frequent Elements
• Find Median from Data Stream
• Merge K Sorted Lists
• Task Scheduler
• K Closest Points to Origin

Frequently Asked Questions

Other K-Way Merge Techniques