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 == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i] is sorted in non-decreasing order.#632 Smallest Range Covering Elements from K Lists asks you to find the smallest numerical range that includes at least one element from each of the given sorted lists. Since each list is already sorted, the key idea is to efficiently track the current minimum and maximum elements across lists.
A common strategy uses a min-heap (priority queue) to always access the smallest element among the current candidates while tracking the current maximum value. Initially, insert the first element of every list into the heap. Then repeatedly pop the smallest element and push the next element from the same list, updating the range if the current window improves the answer.
This greedy technique ensures that every step maintains one element from each list while gradually tightening the range. Because the heap manages ordering efficiently, the approach runs in O(N log K) time where N is the total number of elements and K is the number of lists. The extra space required is O(K) for the heap.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Min Heap / Priority Queue with Greedy Expansion | O(N log K) | O(K) |
| Flatten + Sort + Sliding Window | O(N log N) | O(N) |
NeetCodeIO
In this approach, we use a min-heap to keep track of the smallest element across all lists, and a variable to track the current maximum from the lists. Initially, insert the first element of each list into the heap along with the list index and element index. The range [min, max] is updated as we extract the smallest element from the heap and add the next element from the respective list. The process continues until any one list is exhausted, ensuring the range includes elements from all lists.
Time Complexity: O(n * log k), as each operation on the heap takes O(log k), performed for all elements.
Space Complexity: O(k), where k is the number of lists, due to storage in the heap.
1import heapq
2
3def smallestRange(nums):
4 minHeap = []
5 maxVal = float('-inf')
6 for i in range(len(nums)):
7 heapq.heappush(minHeap, (nums[i][0], i, 0))
8 maxVal = max(maxVal, nums[i][0])
9 rangeStart, rangeEnd = float('-inf'), float('inf')
10 while len(minHeap) == len(nums):
11 minVal, listIndex, elementIndex = heapq.heappop(minHeap)
12 if maxVal - minVal < rangeEnd - rangeStart:
13 rangeStart, rangeEnd = minVal, maxVal
14 if elementIndex + 1 < len(nums[listIndex]):
15 nextVal = nums[listIndex][elementIndex + 1]
16 heapq.heappush(minHeap, (nextVal, listIndex, elementIndex + 1))
17 maxVal = max(maxVal, nextVal)
18 return [rangeStart, rangeEnd]This Python solution uses a min-heap to store the current minimum element along with its list and index. The heapifies the first element of each list and iteratively extracts minimum elements, updating the range when a new smaller range is found. For advanced elements, new entries get pushed into the min-heap. This continues until one list runs out.
In this approach, we maintain an array to store current indices for each list. Similarly, while keeping track of the maximum and minimum values, traverse the lists to update current positions and check the potential range. The update continues as long as all lists contribute a number to the current range.
Time Complexity: O(n * log k) since using a heap.
Space Complexity: O(k) for minimum entries.
1import java.util.PriorityQueue;
2
3Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is considered a classic hard interview question involving heaps, greedy logic, and multi-pointer reasoning. Variations of it have appeared in interviews at large tech companies because it tests both data structures and algorithmic thinking.
A min-heap (priority queue) is the most effective data structure for this problem. It allows quick access to the smallest current element among K lists while tracking the current maximum value to compute candidate ranges efficiently.
The optimal approach typically uses a min-heap (priority queue) combined with a greedy strategy. By always advancing the list that contributes the current minimum element, you maintain a candidate range covering all lists and update the smallest range found so far.
Yes, an alternative method is to flatten all elements with their list indices, sort them, and apply a sliding window that ensures at least one element from each list is included. This approach is intuitive but slightly less efficient due to the sorting step.
This Java solution uses a priority queue to track indices of the elements. The priority queue allows the smallest element across current elements to be easily managed. For any move of the index, it maintains a new input keeping the maximal substantiality in check.