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.
Approach 01:
-
C++
-
Python
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Element {
int rowIndex;
int colIndex;
int value; // nums[rowIndex][colIndex]
};
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& numLists) {
auto compare = [&](const Element& a, const Element& b) { return a.value > b.value; };
priority_queue<Element, vector<Element>, decltype(compare)> minHeap(compare);
int currentMin = INT_MAX;
int currentMax = INT_MIN;
// Initialize the heap with the first element from each list
for (int i = 0; i < numLists.size(); ++i) {
const int value = numLists[i][0];
minHeap.emplace(Element{i, 0, value});
currentMin = min(currentMin, value);
currentMax = max(currentMax, value);
}
int minRange = currentMin;
int maxRange = currentMax;
// Continue processing until the heap contains elements from all lists
while (minHeap.size() == numLists.size()) {
const auto [rowIndex, colIndex, _] = minHeap.top();
minHeap.pop();
if (colIndex + 1 < numLists[rowIndex].size()) {
minHeap.emplace(Element{rowIndex, colIndex + 1, numLists[rowIndex][colIndex + 1]});
currentMax = max(currentMax, numLists[rowIndex][colIndex + 1]);
currentMin = minHeap.top().value;
if (currentMax - currentMin < maxRange - minRange) {
minRange = currentMin;
maxRange = currentMax;
}
}
}
return {minRange, maxRange};
}
};
Time Complexity
- Initializing the heap:
In the beginning, the function inserts the first element from each of the
klists into the heap. This takes \(O(k \log k)\), where \(k\) is the number of lists, because inserting into a heap requires \(O(\log k)\) operations. - Iterating through the elements:
The function processes all the elements across all lists, which totals to
nelements (wherenis the sum of the lengths of all the lists). For each element, it removes the smallest element from the heap (which takes \(O(\log k)\)) and inserts the next element from the same list (also \(O(\log k)\)). Hence, iterating through the elements takes \(O(n \log k)\). - Overall Time Complexity:
The overall time complexity is \(O(n \log k)\), where
nis the total number of elements across all lists, andkis the number of lists.
Space Complexity
- Heap space:
The heap stores at most one element from each of the
klists at any point in time. Therefore, the space complexity of the heap is \(O(k)\). - Auxiliary Space:
A constant amount of extra space is used for variables such as
currentMinandcurrentMax. The function does not use any additional data structures aside from the heap, so the auxiliary space complexity is \(O(1)\). - Overall Space Complexity:
The overall space complexity is \(O(k)\), where
kis the number of lists.
import heapq
class Solution:
def smallestRange(self, numLists: list[list[int]]) -> list[int]:
minHeap = [(row[0], i, 0) for i, row in enumerate(numLists)]
heapq.heapify(minHeap)
currentMax = max(row[0] for row in numLists)
currentMin = heapq.nsmallest(1, minHeap)[0][0]
result = [currentMin, currentMax]
while len(minHeap) == len(numLists):
currentValue, rowIndex, colIndex = heapq.heappop(minHeap)
if colIndex + 1 < len(numLists[rowIndex]):
heapq.heappush(minHeap, (numLists[rowIndex][colIndex + 1], rowIndex, colIndex + 1))
currentMax = max(currentMax, numLists[rowIndex][colIndex + 1])
currentMin = heapq.nsmallest(1, minHeap)[0][0]
if currentMax - currentMin < result[1] - result[0]:
result[0], result[1] = currentMin, currentMax
return result
Time Complexity
- Initializing the heap:
The heap is initialized with the first element from each of the
klists, which takes \(O(k)\). Heapification takes \(O(k \log k)\). - Iterating through the elements:
The algorithm processes all elements across all lists. Each insertion and removal operation in the heap takes \(O(\log k)\), and since there are
nelements (wherenis the total number of elements across all lists), iterating through them requires \(O(n \log k)\). - Overall Time Complexity:
The overall time complexity is \(O(n \log k)\), where
nis the total number of elements across all lists, andkis the number of lists.
Space Complexity
- Heap space:
The heap stores at most one element from each of the
klists at any given time. Thus, the space complexity of the heap is \(O(k)\). - Auxiliary Space:
A constant amount of extra space is used for variables such as
currentMaxandresult. No additional data structures are used, so the auxiliary space complexity is \(O(1)\). - Overall Space Complexity:
The overall space complexity is \(O(k)\), where
kis the number of lists.