Here, We see Smallest Range Covering Elements from K Lists LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Smallest Range Covering Elements from K Lists LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Smallest Range Covering Elements from K Lists LeetCode Solution
Table of Contents
Problem Statement
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]
Smallest Range Covering Elements from K Lists LeetCode Solution C++
class Solution {
public:
struct node {
int data, row, column;
node(int value, int i, int j) : data(value), row(i), column(j) {}
};
struct comparator {
bool operator() (node a, node b) {
return a.data > b.data;
}
};
vector<int> smallestRange(vector<vector<int>>& nums) {
int k = nums.size();
priority_queue<node, vector<node>, comparator> minHeap;
int currMin = INT_MAX, currMax = INT_MIN, currRange = INT_MAX;
for(int i = 0; i < k; ++i) {
currMax = max(currMax, nums[i][0]);
node temp(nums[i][0], i, 0);
minHeap.push(temp);
}
int start = currMin, end = currMax;
while(true) {
node min = minHeap.top();
minHeap.pop();
currMin = min.data;
if(currMax - currMin < currRange) {
start = currMin;
end = currMax;
currRange = currMax - currMin;
}
if(min.column + 1 == nums[min.row].size())
break;
node next(nums[min.row][min.column + 1], min.row, min.column + 1);
minHeap.push(next);
if(next.data > currMax)
currMax = next.data;
}
return {start, end};
}
};
Code language: PHP (php)
Smallest Range Covering Elements from K Lists LeetCode Solution Java
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int[] res = new int[2];
int minx=Integer.MAX_VALUE;
int maxy=Integer.MIN_VALUE;
int minRange=Integer.MAX_VALUE;
PriorityQueue<int[]> pq=new PriorityQueue<>((i,j) ->
i[0] - j[0]
);
for(int i=0;i<nums.size();i++)
{
if(nums.get(i).get(0)>maxy)
maxy=nums.get(i).get(0);
pq.offer(new int[] {nums.get(i).get(0),i,0});
}
while(!pq.isEmpty())
{
int[] min=pq.poll();
int i=min[1];
int j=min[2];
if(maxy-min[0] < minRange)
{
minRange=maxy-min[0];
res[0]=min[0];
res[1]=maxy;
}
if(i<nums.size() && j+1<nums.get(i).size())
{
pq.offer(new int[] {nums.get(i).get(j+1),i,j+1});
if(nums.get(i).get(j+1)>maxy)
maxy=nums.get(i).get(j+1);
}
else
break;
}
return res;
}
}
Code language: PHP (php)
Smallest Range Covering Elements from K Lists LeetCode Solution JavaScript
var smallestRange = function(nums) {
const minPQ = new MinPriorityQueue({
priority: a => a[2]
});
let minRange = Number.MAX_VALUE;
for (let i=0;i<nums.length;i++) {
minPQ.enqueue([i, 0, nums[i][0]]);
}
let ans = [];
while (!minPQ.isEmpty()) {
const range = minPQ.back().element[2] - minPQ.front().element[2];
if (minRange > range) {
minRange = range;
ans = [minPQ.front().element[2], minPQ.back().element[2]];
}
const [listIndex, listIterator, currentValue] = minPQ.front().element;
if (listIterator + 1 < nums[listIndex].length) {
minPQ.dequeue();
minPQ.enqueue([listIndex,listIterator + 1, nums[listIndex][listIterator + 1]]);
} else {
break;
}
}
return ans;
};
Code language: JavaScript (javascript)
Smallest Range Covering Elements from K Lists Solution Python
class Solution(object):
def smallestRange(self, nums):
n = len(nums)
pq = []
ma = 0
for i in range(n):
heappush(pq, (nums[i][0] , i, 0))
ma = max(ma , nums[i][0])
ans = [pq[0][0] , ma]
while True:
_,i,j = heappop(pq)
if j == len(nums[i])-1:
break
next_num = nums[i][j+1]
ma = max( ma , next_num)
heappush(pq,(next_num, i , j+1))
if ma-pq[0][0] < ans[1] - ans[0]:
ans= [pq[0][0], ma]
return ans
Code language: HTML, XML (xml)