Sponsored
Sponsored
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.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5using namespace std;
6
7vector<int> smallestRange(vector<vector<int>>& nums) {
8 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> minHeap;
9 int maxVal = INT_MIN;
10 for (int i = 0; i < nums.size(); i++) {
11 minHeap.push({nums[i][0], i, 0});
12 maxVal = max(maxVal, nums[i][0]);
13 }
14 int rangeStart = numeric_limits<int>::min(), rangeEnd = numeric_limits<int>::max();
15 while (minHeap.size() == nums.size()) {
16 auto [minVal, listIndex, elementIndex] = minHeap.top(); minHeap.pop();
17 if (maxVal - minVal < rangeEnd - rangeStart) {
18 rangeStart = minVal;
19 rangeEnd = maxVal;
20 }
21 if (elementIndex + 1 < nums[listIndex].size()) {
22 int nextVal = nums[listIndex][elementIndex + 1];
23 minHeap.push({nextVal, listIndex, elementIndex + 1});
24 maxVal = max(maxVal, nextVal);
25 }
26 }
27 return {rangeStart, rangeEnd};
28}This C++ solution employs a min-heap to maintain the smallest current elements from each list. Initialization includes adding the first element from each list to the min-heap. The min-heap then helps in determining the smallest current range that can capture one element from each list.
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
3This 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.