Finding the right “window” size is the trickiest part of working with k sorted lists. Each list needs to contribute to the range, and the difference between the smallest and largest integers should be minimal. Many technical interviews feature this question because it assesses your ability to manage multiple pointers and use tools like heaps or priority queues to narrow the search. Mastering this can help you excel in important merging and sliding window techniques for competitive programming.
Also Read – Geometric Algorithms
k Sorted Lists Problem
The goal is clear, but it’s not easy. Suppose you have several sorted lists, each containing integers in order from smallest to largest. You want to find a range [min, max] that meets these criteria:
At least one integer from each sorted list must be in the range.
The smallest valid range has the least gap between the highest and lowest values.
If two ranges have the same difference, the one with the smaller minimum value is better.
Picture that you have three lists:
- List 1: [4, 10, 15]
- List 2: [1, 10, 11]
- List 3: [5, 12, 20]
A range like [1, 20] theoretically has members from all lists, but it is not the shortest. A considerably narrower range would be [10, 12], which has 10 from List 1, 10 from List 2, and 12 from List 3. Only 2 points separate these two.
Examples of Smallest Range in k Sorted Lists
Example 1
Input:
List 1: [4, 10, 15]
List 2: [1, 10, 11]
List 3: [5, 12, 20]
Output:
[10, 12]
Explanation:
This range has 10 (List 1), 10 (List 2), and 12 (List 3) numbers. There isn’t much of a difference (2).
Example 2
Input:
List 1: [1, 5, 8]
List 2: [4, 12]
List 3: [7, 8, 10]
Output:
[4, 7]
Explanation:
The range [4, 7] has at least one member from each list and is the smallest difference conceivable.
Brute Force Approach for k Sorted Lists
In a naive scenario, you might think of comparing every possible combination of elements across the multiple sorted lists. You would choose one item from each list until you have k items. After that, you find the range.
But when the number of elements goes up, the number of combinations goes up by a lot. This means that the brute force strategy doesn’t work well for big datasets or when k is high. Because the lists are already sorted, we can use that to avoid making comparisons that aren’t needed.
Approach Using k Pointers
Before jumping to heaps, there is an intermediate optimisation using k pointers.
Step-by-Step Logic
- Initialise one pointer for each of the sorted lists (all starting at index 0).
- At each step, find the minimum and maximum elements among the current pointers.
- Calculate the current range using these values.
- Move the pointer that points to the minimum element forward.
- Repeat until any one list is exhausted.
Why this works
By always advancing the pointer at the smallest element, you attempt to reduce the gap between the minimum and maximum values. This ensures that the window keeps shifting towards a tighter range.
Also Read – Introduction to Red-Black Tree
Complexity
- Time Complexity: O(n \cdot k^2) (since we scan all pointers repeatedly)
- Space Complexity: O(k)
While this is better than brute force, it is still inefficient compared to the heap-based solution.
Min-Heap Approach for k Sorted List
The most efficient way to solve the multiple sorted lists range problem is by using a Min-Priority Queue (Min-Heap). This allows us to always keep track of the smallest element currently being considered from the lists.
Steps to Solve these Problems
- Initialisation: Create a Min-Heap to store the first element of each of the multiple sorted lists. While doing this, keep track of the maximum value among these k initial elements.
- Current Range: The first range you should look at is the difference between the highest value you just found and the lowest value at the top of the heap.
- Iterative Refinement:
- Pop the smallest element from the Min-Heap.
- This element belonged to a specific list (let’s call it List ‘i’).
- Take the next element from List ‘i’ and push it into the heap.
- Update your running maximum if this new element is larger than the current max.
- Recalculate the range using the new top of the heap (the new minimum) and the updated maximum.
- Completion: Keep doing this until you get to the end of one of the lists. You can’t make a range that contains an element from every list anymore if one list is empty.
Why this works
We are “pushing” the bottom bound of our range forward by always replacing the smallest element in our current collection. We only care about shrinking the range, and since the lists are sorted, the only way to potentially find a smaller range after moving the minimum pointer is to hope the new element from that same list stays close to our current maximum.
Also Read – Advance Data Structure and Algorithms
Python Code for k Sorted Lists Smallest Range
import heapq
def smallest_range(nums):
k = len(nums)
heap = []
current_max = float(‘-inf’)
# Initialize heap
for i in range(k):
val = nums[i][0]
heapq.heappush(heap, (val, i, 0))
current_max = max(current_max, val)
range_start, range_end = -10**5, 10**5
while True:
current_min, list_idx, elem_idx = heapq.heappop(heap)
# Update range
if current_max – current_min < range_end – range_start:
range_start, range_end = current_min, current_max
# Move pointer in same list
if elem_idx + 1 == len(nums[list_idx]):
break
next_val = nums[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
current_max = max(current_max, next_val)
return [range_start, range_end]
Time and Space Complexity
Efficiency is key in k sorted array problems. Let k be the number of lists and n be the average number of items in each list.
- Time Complexity: The heap can only push and pop each piece once. The entire number of items is n \times k, and heap operations require O(\log k) time, therefore the total complexity is O(nk \log k).
- Space Complexity: The heap only holds one item from each list at a time, which takes up O(k) more space.
Comparison of k Sorted List Approaches
Here’s a quick comparison of different approaches to solve these problems based on efficiency and usability.
| Feature | Brute Force | Min-Heap (Optimal) |
| Logic | Check every combination | Track min/max pointers |
| Time Complexity | O(n^k) | O(nk \log k) |
| Space Complexity | O(k) | O(k) |
| Suitability | Only for tiny datasets | Professional/Competitive use |
| Key Advantage | Simple to code | Extremely fast and scalable |
Tips to Solve k Sorted Problems
When coding this for a k sorted array or list problem, remember to store not just the value in the heap, but also the index of the list it came from and the index of the element within that list. This ensures you know exactly which list to pull the next element from.
Using a custom object or a tuple in Python/C++ is generally the best way to keep these three pieces of data (value, list_index, element_index) together.
Common Mistakes in k Sorted Lists Problems
- Exhausting Lists Early: Beginners often forget that the process must stop as soon as any list runs out of elements. You cannot maintain the “at least one element from each list” rule once a list is finished.
- Updating Max Wrongly: Make sure that the maximum is updated every time a new item is added to the heap, not when an item is taken away.
- Tie Breaking: If you find two ranges with the same difference, always check to see if the new min is smaller than the old min to meet conventional competitive programming standards.
FAQs
What happens if the multiple sorted lists have different lengths?
The algorithm works perfectly regardless of list length. The process stops the moment the shortest list is exhausted, as you can no longer satisfy the requirement of having one element from every list.
Why is a Min-Heap used instead of a Max-Heap?
We employ a Min-Heap because we need to keep finding and removing the smallest element in our current window to try to raise the lower bound, which could make the range shorter.
Can this approach be used for a single array?
Yes, the same heap logic works if you need to identify ranges within parts of a huge array, as long as you can regard those parts as separate sorted entities.
Is there a way to solve this without a heap?
You might use a balanced Binary Search Tree (BST), which would have the same O(log k) time complexity for adding and removing items. However, a heap is usually quicker to set up and has less overhead.
How does the k sorted lists merge relate to this?
To compare the heads of different lists, both the "merge" process and the "smallest range" procedure use a Min-Heap. The primary difference is that when you merge, you only output the minimum. Here, you additionally keep track of the maximum to find the range.