# Smallest Range Covering Elements from K Lists **Difficulty:** HARD [External](https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists) Canonical: https://scaleengineer.com/dsa/problems/smallest-range-covering-elements-from-k-lists **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table, Heap (Priority Queue) **Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Lyft](https://scaleengineer.com/companies/lyft), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [WinZO](https://scaleengineer.com/companies/winzo), [Pinterest](https://scaleengineer.com/companies/pinterest) --- ## Problem 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`. **Example 1:** **Input:** nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] **Output:** [20,24] **Explanation:** List 1: [4, 10, 15, 24,26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24]. **Example 2:** **Input:** nums = [[1,2,3],[1,2,3],[1,2,3]] **Output:** [1,1] **Constraints:** * `nums.length == k` * `1 <= k <= 3500` * `1 <= nums[i].length <= 50` * `-105 <= nums[i][j] <= 105` * `nums[i]` is sorted in **non-decreasing** order. # Approaches ## Sliding Window on Merged List This approach transforms the problem into a well-known sliding window problem. First, we combine all elements from the `k` lists into a single, flat list. To keep track of the origin of each element, we store them as pairs of `(value, list_index)`. After sorting this merged list by value, we can iterate through it with a sliding window. The goal is to find the shortest subarray (or window) in this sorted list that contains at least one element from each of the original `k` lists. We expand the window to include more elements and shrink it to find the smallest possible valid range. **Time:** O(N log N), where N is the total number of elements across all lists. The sorting step `O(N log N)` dominates the sliding window traversal, which takes `O(N)` time. · **Space:** O(N), where N is the total number of elements across all lists. This space is required to store the merged list of pairs. **Pros:** The logic is a direct application of the sliding window pattern, which is a common and useful technique.; It's conceptually simpler than the heap-based approach for those more familiar with sliding windows than heaps. **Cons:** The time complexity is dominated by the initial sort of all `N` elements, making it slower than the heap-based approach.; Requires `O(N)` extra space to store the merged list, which can be large if the total number of elements is high. ### Explanation The core idea is to reframe the problem from `k` lists to a single sorted list. By merging all numbers while retaining their original list index, we can apply a standard sliding window technique. 1. **Flatten and Sort**: We create a new list containing all elements from the `k` input lists. Each entry in this new list is a pair `(number, original_list_index)`. We then sort this list based on the `number`. 2. **Sliding Window**: We use two pointers, `left` and `right`, to define our window on the sorted list. We also use a frequency map `counts` of size `k` to track which lists are represented in the current window. 3. **Expand and Check**: We move the `right` pointer to expand the window. For each new element `(num, list_idx)` we add, we increment `counts[list_idx]`. If `counts[list_idx]` becomes 1, it means we have just covered a new list. 4. **Shrink and Update**: Once we have covered all `k` lists, we have a valid range `[sorted_list[left].number, sorted_list[right].number]`. We compare this with our smallest range found so far and update if it's better. Then, we try to find an even smaller range by shrinking the window from the left. We move the `left` pointer, decrementing the count for the element that is leaving the window. If its count drops to zero, our window is no longer valid, and we must go back to expanding with the `right` pointer. This process ensures we check all possible minimal covering ranges. ```java class Solution { public int[] smallestRange(List> nums) { List mergedList = new ArrayList<>(); for (int i = 0; i < nums.size(); i++) { for (int num : nums.get(i)) { mergedList.add(new int[]{num, i}); } } Collections.sort(mergedList, (a, b) -> a[0] - b[0]); int[] result = new int[2]; int minRange = Integer.MAX_VALUE; int k = nums.size(); int[] counts = new int[k]; int listsCovered = 0; int left = 0; for (int right = 0; right < mergedList.size(); right++) { int[] rightElem = mergedList.get(right); int listIndex = rightElem[1]; if (counts[listIndex] == 0) { listsCovered++; } counts[listIndex]++; while (listsCovered == k) { int[] leftElem = mergedList.get(left); int currentRange = rightElem[0] - leftElem[0]; if (currentRange < minRange) { minRange = currentRange; result[0] = leftElem[0]; result[1] = rightElem[0]; } else if (currentRange == minRange && leftElem[0] < result[0]) { result[0] = leftElem[0]; result[1] = rightElem[0]; } int leftListIndex = leftElem[1]; counts[leftListIndex]--; if (counts[leftListIndex] == 0) { listsCovered--; } left++; } } return result; } } ``` ### Algorithm - Create a single list of pairs, where each pair contains a number and the index of the list it came from. - Sort this merged list based on the numbers in ascending order. - Initialize a sliding window using two pointers, `left` and `right`, both starting at the beginning of the sorted list. - Use a frequency map or an array `counts` to keep track of how many elements from each of the `k` lists are currently inside the window. - Expand the window by incrementing the `right` pointer. For each element added, update the `counts`. - When the window contains at least one element from every list (i.e., all counts are >= 1), it's a valid covering range. - Once a valid range is found, try to shrink it from the left by incrementing the `left` pointer. As long as the window remains valid, keep shrinking and updating the smallest range found so far. - If shrinking makes the window invalid (a list is no longer represented), stop shrinking and continue expanding the window with the `right` pointer. - Repeat the process until the `right` pointer has traversed the entire merged list. ## Optimized Approach using Min-Heap This is a more efficient approach that avoids sorting all the elements. It works by maintaining a 'window' of `k` elements, one from each list. A min-heap is used to efficiently find the minimum element within this window. The range is defined by the minimum and maximum elements currently in our set of `k` elements. We start with the first element from each list. Then, we iteratively remove the overall minimum element and replace it with the next element from its own list. By doing this, we 'slide' our window through the lists, always advancing the pointer of the list that contains the current minimum. This process guarantees that we explore all potential ranges in an optimized manner. **Time:** O(N log k), where N is the total number of elements and k is the number of lists. Each of the N elements is added to and removed from the heap once, and each heap operation takes O(log k) time. · **Space:** O(k), where k is the number of lists. The space is used by the min-heap to store one element from each list. **Pros:** Optimal time complexity, as it avoids a full sort of all `N` elements.; Excellent space complexity, as the heap only ever stores `k` elements. **Cons:** The implementation can be slightly more complex due to managing the heap and tracking multiple indices simultaneously. ### Explanation This approach cleverly uses a min-heap to maintain a sliding window across the `k` sorted lists without merging them. 1. **Initialization**: We create a min-heap that will store one element from each list. We populate it with the first element from all `k` lists. Each item in the heap is an array or object containing the element's value, its list index, and its index within that list, e.g., `{value, listIdx, elementIdx}`. We also track the maximum value (`maxVal`) among these initial `k` elements. 2. **First Range**: After initialization, the heap's top element is the minimum of the current window, and `maxVal` is the maximum. This gives us our first potential answer for the smallest range. 3. **Iterative Improvement**: We then enter a loop. In each step: a. We extract the minimum element from the heap. Let's say it came from `list_i`. b. The range formed by this minimum element and the current `maxVal` is a candidate for the smallest range. We compare it with our best-so-far and update if necessary. c. We then take the *next* element from `list_i` (if it exists) and add it to the heap. d. When adding the new element, we update `maxVal` to be the maximum of itself and the new element's value. 4. **Termination**: The loop terminates when we extract an element from a list that has no more elements to offer. At this point, it's impossible to form a new range that covers all `k` lists, so we must have already found the smallest one. This method is more efficient because instead of a full sort, we only perform `log k` work for each element we process. ```java class Solution { public int[] smallestRange(List> nums) { // Min-heap to store {value, listIndex, elementIndex} PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); int maxVal = Integer.MIN_VALUE; int k = nums.size(); // Initialize the heap with the first element from each list for (int i = 0; i < k; i++) { int val = nums.get(i).get(0); minHeap.offer(new int[]{val, i, 0}); maxVal = Math.max(maxVal, val); } int rangeStart = -1; int rangeEnd = -1; int minRange = Integer.MAX_VALUE; while (true) { int[] minElem = minHeap.poll(); int val = minElem[0]; int listIndex = minElem[1]; int elementIndex = minElem[2]; // Check if current range is smaller if (maxVal - val < minRange) { minRange = maxVal - val; rangeStart = val; rangeEnd = maxVal; } else if (maxVal - val == minRange && val < rangeStart) { rangeStart = val; rangeEnd = maxVal; } // If we've exhausted any list, we can't find a better range if (elementIndex + 1 == nums.get(listIndex).size()) { break; } // Add the next element from the same list to the heap int nextVal = nums.get(listIndex).get(elementIndex + 1); minHeap.offer(new int[]{nextVal, listIndex, elementIndex + 1}); // Update the max value in the current window maxVal = Math.max(maxVal, nextVal); } return new int[]{rangeStart, rangeEnd}; } } ``` ### Algorithm - Create a min-heap (PriorityQueue) to keep track of the current smallest element among the `k` lists. - Initialize the heap by adding the first element from each of the `k` lists. The heap will store tuples of `(value, list_index, element_index)`. - While initializing, also keep track of the maximum value (`maxVal`) among these first `k` elements. - The initial range is `[heap.peek().value, maxVal]`. This is our first candidate for the smallest range. - Enter a loop that continues as long as we can form a valid window (i.e., no list has been exhausted). - In each iteration, extract the minimum element from the heap. Let its value be `minVal`. - The current range under consideration is `[minVal, maxVal]`. Compare it with the best range found so far and update if it's smaller. - Take the next element from the list that the `minVal` came from. - Add this new element to the heap and update `maxVal` to be the maximum of the old `maxVal` and the new element's value. - If any list runs out of elements, we can no longer form a range covering all `k` lists, so we break the loop and return the best range found. # Solutions ### Java ```java class Solution { public int[] smallestRange(List> nums) { int n = 0; for (var v : nums) { n += v.size(); } int[][] t = new int[n][2]; int k = nums.size(); for (int i = 0, j = 0; i < k; ++i) { for (int x : nums.get(i)) { t[j++] = new int[]{x, i}; } } Arrays.sort(t, (a, b)->a[0] - b[0]); int j = 0; Map cnt = new HashMap<>(); int[] ans = new int[]{-1000000, 1000000}; for (int[] e : t) { int b = e[0]; int v = e[1]; cnt.put(v, cnt.getOrDefault(v, 0) + 1); while (cnt.size() == k) { int a = t[j][0]; int w = t[j][1]; int x = b - a - (ans[1] - ans[0]); if (x < 0 || (x == 0 && a < ans[0])) { ans[0] = a; ans[1] = b; } cnt.put(w, cnt.get(w) - 1); if (cnt.get(w) == 0) { cnt.remove(w); } ++j; } } return ans; } } ``` ### CPP ```cpp class Solution { public: vector smallestRange(vector> &nums) { int n = 0; for (auto &v : nums) n += v.size(); vector> t(n); int k = nums.size(); for (int i = 0, j = 0; i < k; ++i) { for (int v : nums[i]) { t[j++] = {v, i}; } } sort(t.begin(), t.end()); int j = 0; unordered_map cnt; vector ans = {-1000000, 1000000}; for (int i = 0; i < n; ++i) { int b = t[i].first; int v = t[i].second; ++cnt[v]; while (cnt.size() == k) { int a = t[j].first; int w = t[j].second; int x = b - a - (ans[1] - ans[0]); if (x < 0 || (x == 0 && a < ans[0])) { ans[0] = a; ans[1] = b; } if (--cnt[w] == 0) { cnt.erase(w); } ++j; } } return ans; } }; ``` ### Python ```python class Solution: def smallestRange(self, nums: List[List[int]]) -> List[int]: t = [(x, i) for i, v in enumerate(nums) for x in v] t . sort() cnt = Counter() ans = [- inf, inf] j = 0 for b, v in t: cnt[v] += 1 while len(cnt) == len(nums): a = t[j][0] x = b - a - (ans[1] - ans[0]) if x < 0 or (x == 0 and a < ans[0]): ans = [a, b] w = t[j][1] cnt[w] -= 1 if cnt[w] == 0: cnt . pop(w) j += 1 return ans ```