Algorithm
Problem Name: 632. 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-105 <= nums[i][j] <= 105nums[i]is sorted in non-decreasing order.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> smallestRange(vector < vector<int>>& nums) {
vector<int>res(2);
auto comp = [](vector<int>& a, vector<int>& b){ return a[0] > b[0]; };
priority_queue < vector<int>, vector < vector<int>>, decltype(comp)>pq(comp);
int lo = 0, hi = 0, minRange = INT_MAX;
for(int i = 0; i < nums.size(); i++) hi = max(hi, nums[i][0]), pq.push({nums[i][0], 0, i});
while(true){
auto v = pq.top();
pq.pop();
lo = v[0];
if(hi - lo < minRange){
minRange = min(minRange, hi - lo);
res[0] = lo;
res[1] = hi;
}
if(++v[1] == nums[v[2]].size()) break;
v[0] = nums[v[2]][v[1]];
pq.push(v);
hi = max(hi, v[0]>;
}
return res;
}
};
Input
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output
[20,24]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const smallestRange = function(nums) {
if (nums.length === 1) return [nums[0], nums[0]]
const pq = new PQ((a, b) => a.v < b.v)
let min = Number.MAX_SAFE_INTEGER
let max = Number.MIN_SAFE_INTEGER
for (let i = 0; i < nums.length; i++) {
if (nums[i].length > 0) {
const top = nums[i].shift()
pq.push({ v: top, i })
min = Math.min(min, top)
max = Math.max(max, top)
}
}
let bestRange = [min, max]
while (pq.size() > 0) {
const { v, i } = pq.pop()
if (nums[i].length === 0) return bestRange
const newVal = nums[i].shift()
pq.push({ v: newVal, i })
min = pq.peek().v
max = Math.max(max, newVal)
if (max - min < bestRange[1] - bestRange[0]) {
bestRange = [min, max]
}
}
return bestRange
}
function PQ(f) {
this.q = []
this.f = f
}
PQ.prototype.size = function() {
return this.q.length
}
PQ.prototype.peek = function() {
return this.q[0]
}
PQ.prototype.push = function(v) {
const q = this.q
let i = q.length
q.push(v)
let parent = Math.floor((i - 1) / 2)
while (parent >= 0 && this.f(q[i], q[parent])) {
this.swap(i, parent)
i = parent
parent = Math.floor((i - 1) / 2)
}
}
PQ.prototype.pop = function() {
const q = this.q
if (q.length === 0) return null
this.swap(0, q.length - 1)
let i = 0
let lc = 1
let rc = 2
while (lc < q.length - 1) {
let r = i
if (this.f(q[lc], q[r])) {
r = lc
}
if (rc < q.length - 1 && this.f(q[rc], q[r])) {
r = rc
}
if (r === i) break
this.swap(i, r)
i = r
lc = i * 2 + 1
rc = i * 2 + 2
}
return q.pop()
}
PQ.prototype.swap = function(i, j) {
const q = this.q
const t = q[i]
q[i] = q[j]
q[j] = t
}
Input
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output
[20,24]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def smallestRange(self, nums):
L = R = None
while True:
mn = mx = nums[0][-1]
ind = [0]
for i, ls in enumerate(nums[1:]):
if ls[-1] > mx:
mx, ind = ls[-1], [i + 1]
elif ls[-1] == mx:
ind.append(i + 1)
elif ls[-1] < mn:
mn = ls[-1]
if L == None or mx - mn <= R - L:
L, R = mn, mx
for j in ind:
nums[j].pop()
if not nums[j]:
return [L, R]
Input
nums = [[1,2,3],[1,2,3],[1,2,3]]
Output
[1,1]