Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Smallest Range Covering Elements from K Lists

Smallest Range Covering Elements from K Lists

Master this topic with zero to advance depth.

Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c, or a < c if b - a == d - c.

Visual Representation

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] Initial elements from each list: {4, 0, 5} Range: [0, 5], Size: 5 To find a smaller range, we must increase the minimum (0). Next element from List 1 (was 0): 9 Set: {4, 9, 5} Range: [4, 9], Size: 5 (same size, but 4 > 0, so not 'smaller' by definition) Next element from List 0 (was 4): 10 Set: {10, 9, 5} Range: [5, 10], Size: 5 ... Eventually we find [20, 24], Size: 4.
Hard

Examples

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]
Approach 1

Level I: Brute Force - Check All Pairs

Intuition

Pick every possible number from the lists as a potential 'start' and every other number as a potential 'end'. For each range [start, end], check if it contains at least one number from each of the k lists. Keep track of the smallest such range.

⏱ O(N^3) where N is the total number of elements. O(N^2) pairs * O(N) check.💾 O(1) extra space

Detailed Dry Run

nums = [[4,10],[0,9],[5,18]] Pairs: [0,4], [0,5], [0,9], [0,10], [4,5], [4,9]... Range [0,5]: Contains 4(L0), 0(L1), 5(L2). Valid. Size 5. Range [4,9]: Contains 4(L0), 9(L1), 5(L2). Valid. Size 5. ...

java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> all = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (int val : nums.get(i)) all.add(new int[]{val, i});
        }
        
        int[] best = { -1000000, 1000000 };
        for (int i = 0; i < all.size(); i++) {
            for (int j = i; j < all.size(); j++) {
                int minVal = Math.min(all.get(i)[0], all.get(j)[0]);
                int maxVal = Math.max(all.get(i)[0], all.get(j)[0]);
                
                if (isValid(nums, minVal, maxVal)) {
                    if (maxVal - minVal < best[1] - best[0]) {
                        best[0] = minVal; best[1] = maxVal;
                    }
                }
            }
        }
        return best;
    }
    
    private boolean isValid(List<List<Integer>> nums, int start, int end) {
        for (List<Integer> list : nums) {
            boolean found = false;
            for (int val : list) {
                if (val >= start && val <= end) {
                    found = true; break;
                }
            }
            if (!found) return false;
        }
        return true;
    }
}
Approach 2

Level II: Sliding Window on All Elements

Intuition

Merge all numbers into a single sorted list, keeping track of which list each number came from. Now the problem becomes: find the shortest subarray in this merged list that contains at least one number from every original list. This is a classic sliding window problem (similar to 'Smallest Window Containing All Characters').

⏱ O(N log N) to sort the merged list, and O(N) for the sliding window.💾 O(N) to store the merged list.

Detailed Dry Run

nums = [[4,10],[0,9],[5,18]] Merged: [(0,L1), (4,L0), (5,L2), (9,L1), (10,L0), (18,L2)] Window [0, 5]: L1, L0, L2 present. Size 5-0=5. Window [4, 9]: L0, L2, L1 present. Size 9-4=5. Window [5, 10]: L2, L1, L0 present. Size 10-5=5. Window [9, 18]: L1, L0, L2 present. Size 18-9=9.

java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> all = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (int val : nums.get(i)) all.add(new int[]{val, i});
        }
        all.sort((a,b) -> a[0] - b[0]);
        
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, k = nums.size();
        int[] res = {-1000000, 1000000};
        
        for (int right = 0; right < all.size(); right++) {
            int listIdx = all.get(right)[1];
            count.put(listIdx, count.getOrDefault(listIdx, 0) + 1);
            
            while (count.size() == k) {
                int curRange = all.get(right)[0] - all.get(left)[0];
                if (curRange < res[1] - res[0]) {
                    res[0] = all.get(left)[0]; res[1] = all.get(right)[0];
                }
                int lIdx = all.get(left)[1];
                count.put(lIdx, count.get(lIdx) - 1);
                if (count.get(lIdx) == 0) count.remove(lIdx);
                left++;
            }
        }
        return res;
    }
}
Approach 3

Level III: K-Way Min-Heap Search (Optimal)

Intuition

To find the smallest range, we need to track one element from each list. We maintain these k elements in a Min-Heap. The current range is defined by [min_in_heap, max_in_heap]. To try and find a smaller range, we must increase the minimum element by popping it and replacing it with the next element from that same list. As we go, we keep track of the maximum value currently in our set to update the range.

⏱ O(N log K) where N is the total number of elements and K is the number of lists.💾 O(K) for the Min-Heap.

Detailed Dry Run

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] Heap = [(0,L1,idx0), (4,L0,idx0), (5,L2,idx0)]. MaxVal = 5. Range = [0, 5], Size 5.

  1. Pop 0. Next L1 is 9. Heap=[(4,0,0), (5,2,0), (9,1,1)]. MaxVal = 9. Range=[4,9], Size 5.
  2. Pop 4. Next L0 is 10. Heap=[(5,2,0), (9,1,1), (10,0,1)]. MaxVal = 10. Range=[5,10], Size 5.
  3. Pop 5. Next L2 is 18. Heap=[(9,1,1), (10,0,1), (18,2,1)]. MaxVal = 18. Range=[9,18], Size 9. ... Eventually we hit [20, 24].
java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // {value, row, col}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int maxVal = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            maxVal = Math.max(maxVal, val);
        }
        
        int[] res = { -1000000, 1000000 };
        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            int minVal = curr[0], row = curr[1], col = curr[2];
            
            if (maxVal - minVal < res[1] - res[0]) {
                res[0] = minVal; res[1] = maxVal;
            }
            
            if (col + 1 < nums.get(row).size()) {
                int nextVal = nums.get(row).get(col + 1);
                minHeap.offer(new int[]{nextVal, row, col + 1});
                maxVal = Math.max(maxVal, nextVal);
            }
        }
        return res;
    }
}
← Previous QuestionData Stream as Disjoint Intervals
Next Question →Kth Smallest Prime Fraction