## 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 == k`
• `1 <= k <= 3500`
• `1 <= nums[i].length <= 50`
• `-105 <= nums[i][j] <= 105`
• `nums[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;
}
};
``````
Copy The Code &

Input

cmd
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Output

cmd
[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
}
``````
Copy The Code &

Input

cmd
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Output

cmd
[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]
``````
Copy The Code &

Input

cmd
nums = [[1,2,3],[1,2,3],[1,2,3]]

Output

cmd
[1,1]