Smallest Range Covering Elements from K Lists

Hard

#0586Time: 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.6 companies

Patterns

Sliding Window Greedy

Algorithms

Sorting

Data structures

Array Hash Table Heap (Priority Queue)

Companies

Flipkart Lyft PhonePe Databricks

Prompt

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
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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.
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.
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.
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.

1class Solution {2    public int[] smallestRange(List<List<Integer>> nums) {3        List<int[]> mergedList = new ArrayList<>();4        for (int i = 0; i < nums.size(); i++) {5            for (int num : nums.get(i)) {6                mergedList.add(new int[]{num, i});7            }8        }9 10        Collections.sort(mergedList, (a, b) -> a[0] - b[0]);11 12        int[] result = new int[2];13        int minRange = Integer.MAX_VALUE;14        int k = nums.size();15        int[] counts = new int[k];16        int listsCovered = 0;17        int left = 0;18 19        for (int right = 0; right < mergedList.size(); right++) {20            int[] rightElem = mergedList.get(right);21            int listIndex = rightElem[1];22            23            if (counts[listIndex] == 0) {24                listsCovered++;25            }26            counts[listIndex]++;27 28            while (listsCovered == k) {29                int[] leftElem = mergedList.get(left);30                int currentRange = rightElem[0] - leftElem[0];31 32                if (currentRange < minRange) {33                    minRange = currentRange;34                    result[0] = leftElem[0];35                    result[1] = rightElem[0];36                } else if (currentRange == minRange && leftElem[0] < result[0]) {37                    result[0] = leftElem[0];38                    result[1] = rightElem[0];39                }40 41                int leftListIndex = leftElem[1];42                counts[leftListIndex]--;43                if (counts[leftListIndex] == 0) {44                    listsCovered--;45                }46                left++;47            }48        }49        return result;50    }51}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

This approach cleverly uses a min-heap to maintain a sliding window across the k sorted lists without merging them.

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.
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.
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.
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.

1class Solution {2    public int[] smallestRange(List<List<Integer>> nums) {3        // Min-heap to store {value, listIndex, elementIndex}4        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);5        int maxVal = Integer.MIN_VALUE;6        int k = nums.size();7 8        // Initialize the heap with the first element from each list9        for (int i = 0; i < k; i++) {10            int val = nums.get(i).get(0);11            minHeap.offer(new int[]{val, i, 0});12            maxVal = Math.max(maxVal, val);13        }14 15        int rangeStart = -1;16        int rangeEnd = -1;17        int minRange = Integer.MAX_VALUE;18 19        while (true) {20            int[] minElem = minHeap.poll();21            int val = minElem[0];22            int listIndex = minElem[1];23            int elementIndex = minElem[2];24 25            // Check if current range is smaller26            if (maxVal - val < minRange) {27                minRange = maxVal - val;28                rangeStart = val;29                rangeEnd = maxVal;30            } else if (maxVal - val == minRange && val < rangeStart) {31                rangeStart = val;32                rangeEnd = maxVal;33            }34 35            // If we've exhausted any list, we can't find a better range36            if (elementIndex + 1 == nums.get(listIndex).size()) {37                break;38            }39 40            // Add the next element from the same list to the heap41            int nextVal = nums.get(listIndex).get(elementIndex + 1);42            minHeap.offer(new int[]{nextVal, listIndex, elementIndex + 1});43            44            // Update the max value in the current window45            maxVal = Math.max(maxVal, nextVal);46        }47 48        return new int[]{rangeStart, rangeEnd};49    }50}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] smallestRange(List<List<Integer>> nums) {4    int n = 0;5    for (var v : nums) {6      n += v.size();7    }8    int[][] t = new int[n][2];9    int k = nums.size();10    for (int i = 0, j = 0; i < k; ++i) {11      for (int x : nums.get(i)) {12        t[j++] = new int[]{x, i};13      }14    }15    Arrays.sort(t, (a, b)->a[0] - b[0]);16    int j = 0;17    Map<Integer, Integer> cnt = new HashMap<>();18    int[] ans = new int[]{-1000000, 1000000};19    for (int[] e : t) {20      int b = e[0];21      int v = e[1];22      cnt.put(v, cnt.getOrDefault(v, 0) + 1);23      while (cnt.size() == k) {24        int a = t[j][0];25        int w = t[j][1];26        int x = b - a - (ans[1] - ans[0]);27        if (x < 0 || (x == 0 && a < ans[0])) {28          ans[0] = a;29          ans[1] = b;30        }31        cnt.put(w, cnt.get(w) - 1);32        if (cnt.get(w) == 0) {33          cnt.remove(w);34        }35        ++j;36      }37    }38    return ans;39  }40}

1class Solution {2public:3  vector<int> smallestRange(vector<vector<int>> &nums) {4    int n = 0;5    for (auto &v : nums)6      n += v.size();7    vector<pair<int, int>> t(n);8    int k = nums.size();9    for (int i = 0, j = 0; i < k; ++i) {10      for (int v : nums[i]) {11        t[j++] = {v, i};12      }13    }14    sort(t.begin(), t.end());15    int j = 0;16    unordered_map<int, int> cnt;17    vector<int> ans = {-1000000, 1000000};18    for (int i = 0; i < n; ++i) {19      int b = t[i].first;20      int v = t[i].second;21      ++cnt[v];22      while (cnt.size() == k) {23        int a = t[j].first;24        int w = t[j].second;25        int x = b - a - (ans[1] - ans[0]);26        if (x < 0 || (x == 0 && a < ans[0])) {27          ans[0] = a;28          ans[1] = b;29        }30        if (--cnt[w] == 0) {31          cnt.erase(w);32        }33        ++j;34      }35    }36    return ans;37  }38};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem