← Back to Index

📚 Smallest Range Covering Elements from K Lists – Java Cheat Sheet

📌 What Is It?

The Smallest Range Covering Elements from K Lists problem involves finding the smallest range [x, y] such that at least one number from each of the K lists is included in the range.

This problem can be solved using a min-heap to track the smallest elements across the lists.

🧱 Pattern Template

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> nums.get(a[0]).get(a[1]) - nums.get(b[0]).get(b[1])
        );

        int max = Integer.MIN_VALUE;
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

        // Step 1: Add the first element of each list to the heap
        for (int i = 0; i < nums.size(); i++) {
            minHeap.offer(new int[]{i, 0});
            max = Math.max(max, nums.get(i).get(0));
        }

        // Step 2: Process the heap
        while (minHeap.size() == nums.size()) {
            int[] smallest = minHeap.poll();
            int row = smallest[0], col = smallest[1];
            int min = nums.get(row).get(col);

            // Update the range
            if (max - min < rangeEnd - rangeStart) {
                rangeStart = min;
                rangeEnd = max;
            }

            // Add the next element from the same list to the heap
            if (col + 1 < nums.get(row).size()) {
                minHeap.offer(new int[]{row, col + 1});
                max = Math.max(max, nums.get(row).get(col + 1));
            }
        }

        return new int[]{rangeStart, rangeEnd};
    }
}

📊 Time Complexity

• Heap Operations: O(N log K) – Adding and removing elements from the heap, where N is the total number of elements across all lists.
• Overall Complexity: O(N log K).

✅ Use Cases

• Finding ranges that cover elements from multiple lists
• Applications in scheduling and resource allocation
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 632. Smallest Range Covering Elements from K Lists [Hard] Heap

🧪 Example: Smallest Range Covering Elements from K Lists

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

Explanation:
- The range [20, 24] includes at least one number from each list.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest elements across lists.
• Edge cases: lists with varying lengths, empty lists.
• Ensure the heap stores enough information to track the source of each element.