Smallest Range Covering Elements from K Lists
Smallest Range Covering Elements from K Lists:
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-10^5 <= nums[i][j] <= 10^5nums[i]is sorted in non-decreasing order.
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public int[] smallestRange(List<List<Integer>> nums) {
int[] result = new int[2];
int distance = Integer.MAX_VALUE;
TreeSet<int[]> treeSet = new TreeSet<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
for(int i = 0; i < nums.size(); ++i){
treeSet.add(new int[]{ nums.get(i).get(0), i, 0 }); // value, list, index
}
while(treeSet.size() == nums.size()){
int min = treeSet.first()[0];
int max = treeSet.last()[0];
if(distance > max - min){
distance = max - min;
result[0] = min;
result[1] = max;
}
int[] currentMin = treeSet.pollFirst();
if(nums.get(currentMin[1]).size() > currentMin[2] + 1){
treeSet.add(new int[]{ nums.get(currentMin[1]).get(currentMin[2] + 1), currentMin[1], currentMin[2] + 1 });
}
}
return result;
}
/**
* @param {number[][]} nums
* @return {number[]}
*/
var smallestRange = function (nums) {
const minHeap = new MinPriorityQueue({ priority: (a) => a[0] });
let rangeStart = 0;
let rangeEnd = Infinity;
let maxNumber = -Infinity;
for (let num of nums) {
minHeap.enqueue([num[0], 0, num]);
maxNumber = Math.max(maxNumber, num[0]);
}
while (minHeap.size() == nums.length) {
let [num, i, list] = minHeap.dequeue().element;
if (rangeEnd - rangeStart > maxNumber - num) {
rangeStart = num;
rangeEnd = maxNumber;
}
if (list.length > i + 1) {
minHeap.enqueue([list[i + 1], i + 1, list]);
maxNumber = Math.max(maxNumber, list[i + 1]);
}
}
return [rangeStart, rangeEnd];
};
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
heap=[]
maxvalue=0
for i in range(len(nums)):
heapq.heappush(heap,[nums[i][0],i,0])
maxvalue=max(maxvalue,nums[i][0])
answer=[heap[0][0],maxvalue]
while True:
_,row,col=heapq.heappop(heap)
if col==len(nums[row])-1:
break
next_num=nums[row][col+1]
heapq.heappush(heap,[next_num,row,col+1])
maxvalue=max(maxvalue,next_num)
if maxvalue-heap[0][0]<answer[1]-answer[0]:
answer=[heap[0][0],maxvalue]
return answer
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
const int listSize = nums.size();
multimap<int, int> selectedNumToIndex;
for (int i = 0; i < listSize; i++) {
selectedNumToIndex.insert({nums[i].front(), i});
}
vector<int> selectedNumIndexes(listSize, 0);
vector<int> result = {-100000, 100000};
while (true) {
const auto minIt = selectedNumToIndex.begin();
const auto maxIt = selectedNumToIndex.rbegin();
const int minVal = minIt->first;
const int maxVal = maxIt->first;
const int minListIndex = minIt->second;
if (maxVal - minVal < result[1] - result[0]) {
result[0] = minVal;
result[1] = maxVal;
}
selectedNumToIndex.erase(minIt);
const int newIndex = selectedNumIndexes[minListIndex]++;
const auto &numsList = nums[minListIndex];
if (newIndex >= numsList.size()) break;
selectedNumToIndex.insert({numsList[newIndex], minListIndex});
}
return result;
}
};
Time/Space Complexity:
- Time Complexity: O(nlogk)
- Space Complexity: O(k)
Explanation:
The are two things to do to solve the problem:
- The lists are sorted in non-decreasing order.
- The smallest range, the first element from list A will see is the range it forms with the first elements of list B and C (assuming 3 lists). In other words, if we keep track of the minimum of elements from all lists, we know that's already the best solution containing that element, so we can discard it and replace it with the next element from the list we found the element in.
In the solution we have used TreeSet which just has an advantage of logk min and max operations since we need both boundaries to calculate the range, but it's straightforward to implement minHeap while tracking a local max variable. The first candidates will be the first element from all the lists. We use the triple value, list, index to track from which list and what position did we get the current number. We also track the current minimal distance of the range and both of its boundaries with two variables distance and result (which is returned as result of the algorithm). We iterate over the lists until we reach the end of the smallest one (or all of them if they're of equal size). Each time we get the min and max from the candidates and see if we have a better range that covers elements from all lists. We poll the minimum element and see if we have more elements from the list the minimum element comes from. If yes, we add it to the treeset and continue iterating hoping to find a better range. If the size of the tree is smaller than the number of lists, it means we have reached the end of one of our lists, so there is no point on going forward with the rest of the lists (check the second point from the beginning of the explanation again). We have a TreeSet of size k which leads to O(k) space complexity, and for time complexity at worst case we traverse through all lists (n is sum of lengths of all lists given to us as an input) and for each of iteration we are doing 4 operations on the treeset leading to O(n * 4 logk) = O(nlogk) time complexity.