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.Problem Overview: You are given k sorted lists of integers. The goal is to find the smallest numerical range [a, b] such that each list contributes at least one element inside that range. If multiple ranges have the same width, the one with the smaller start value is preferred.
Approach 1: Flatten + Sliding Window (Sorting) (Time: O(N log N), Space: O(N))
Combine all elements from the k lists into a single array of pairs (value, listIndex). Sort this array by value using sorting. Now apply a sliding window across the sorted array while tracking how many unique lists are covered inside the window. Expand the right pointer to include elements and shrink the left pointer once all k lists are represented. Each valid window forms a candidate range. Update the best range whenever the window length becomes smaller.
Approach 2: Min-Heap with K Pointers (Greedy) (Time: O(N log K), Space: O(K))
This is the optimal solution and uses a min-heap (priority queue). Insert the first element from each list into the heap along with its list index and element index. Track the current maximum value among these elements. The heap always exposes the smallest value across the lists. That smallest value forms the left boundary of the candidate range while the tracked maximum forms the right boundary. Pop the smallest element, push the next element from the same list, and update the maximum if needed. The moment one list runs out of elements, you stop because every valid range must include one element from each list.
Approach 3: Tracking Indices of Current Elements (Multi-Pointer) (Time: O(N log K), Space: O(K))
Maintain an index pointer for each list. At every step, compute the minimum and maximum values among the current pointers. That pair forms the current candidate range. Move the pointer belonging to the minimum value because expanding the smaller boundary is the only way to possibly reduce the range width. Efficient implementations use a heap to quickly identify the smallest pointer value while maintaining the current maximum. The process continues until any pointer reaches the end of its list.
Recommended for interviews: The min-heap greedy solution is what interviewers typically expect. It demonstrates strong understanding of heaps, multi-list merging patterns, and greedy range updates. The flatten + sliding window technique is easier to reason about and proves correctness, but the heap approach improves the time complexity from O(N log N) to O(N log K), which matters when many lists are involved.
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.
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.
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.
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.
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.
Java
JavaScript
Time Complexity: O(n * log k) since using a heap.
Space Complexity: O(k) for minimum entries.
We construct a data item (x, i) for each number x and its group i, and store these items in a new array t. Then, we sort t by the value of the numbers (similar to merging multiple sorted arrays into a new sorted array).
Next, we traverse each data item in t, focusing on the group to which each number belongs. We use a hash table to record the groups of numbers within the sliding window. If the number of groups is k, it means the current window meets the problem's requirements. At this point, we calculate the start and end positions of the window and update the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the total number of numbers in all arrays.
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Using Min-Heap and Two Pointers | Time Complexity: O(n * log k), as each operation on the heap takes O(log k), performed for all elements. |
| Tracking Indices of Current Elements | Time Complexity: O(n * log k) since using a heap. |
| Sorting + Sliding Window | — |
| Priority Queue (Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten + Sliding Window | O(N log N) | O(N) | When implementation simplicity matters and memory for storing all elements is acceptable |
| Min-Heap with K Pointers | O(N log K) | O(K) | Best general solution when lists are already sorted and K is smaller than total elements |
| Tracking Indices (Multi-Pointer) | O(N log K) | O(K) | Useful conceptual model for understanding the greedy range expansion strategy |
Smallest Range Covering Elements from K Lists - Leetcode 632 - Python • NeetCodeIO • 18,778 views views
Watch 9 more video solutions →Practice Smallest Range Covering Elements from K Lists with our built-in code editor and test cases.
Practice on FleetCode