# 632. Smallest Range Covering Elements from K Lists

You have `k` lists of sorted integers in ascending 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:[[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].
``````

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= `k` <= 3500
3. -105 <= `value of elements` <= 105.
4. For Java users, please note that the input type has been changed to List<List>. And after you reset the code template, you’ll see this point.

``````class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
vector<int> res;
vector<pair<int, int>> v;
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
for (int num : nums[i]) {
v.push_back({num, i});
}
}
sort(v.begin(), v.end());
int left = 0, n = v.size(), k = nums.size(), cnt = 0, diff = INT_MAX;
for (int right = 0; right < n; ++right) {
if (m[v[right].second] == 0) ++cnt;
++m[v[right].second];
while (cnt == k && left <= right) {
if (diff > v[right].first - v[left].first) {
diff = v[right].first - v[left].first;
res = {v[left].first, v[right].first};
}
if (--m[v[left].second] == 0) --cnt;
++left;
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int curMax = INT_MIN, n = nums.size();
vector<int> idx(n, 0);
auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > q(cmp);
for (int i = 0; i < n; ++i) {
q.push({nums[i][0], i});
idx[i] = 1;
curMax = max(curMax, nums[i][0]);
}
vector<int> res{q.top().first, curMax};
while (idx[q.top().second] < nums[q.top().second].size()) {
int t = q.top().second; q.pop();
q.push({nums[t][idx[t]], t});
curMax = max(curMax, nums[t][idx[t]]);
++idx[t];
if (res[1] - res[0] > curMax - q.top().first) {
res = {q.top().first, curMax};
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/632

Minimum Window Substring

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104893/Java-Code-using-PriorityQueue.-similar-to-merge-k-array

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation