# 35ms C++ solution beats than 99% submissions

• Similar to merge k sorted list, but using map instead of priority_queue since we need to retrieve both min and max.
Early out if one of the array reaches its end.

``````
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
map<int, queue<int>> m;
for (int i = 0; i < nums.size(); i++) m[nums[i][0]].push(i);
vector<int> index(nums.size(), 0);
vector<int> range = {m.begin()->first, m.rbegin()->first};
int rmin = INT_MAX;

while (!m.empty()) {
if (rmin < INT_MAX) {
if (m.rbegin()->first - rmin < range[1] - range[0]) {
range[0] = rmin;
range[1] = m.rbegin()->first;
}
else return range;
}
else if (m.rbegin()->first - m.begin()->first < range[1] - range[0]) {
range[0] = m.begin()->first;
range[1] = m.rbegin()->first;
}
auto it = m.begin();
queue<int>& q = it->second;
int i = q.front(); q.pop();
if (q.empty()) m.erase(it);
int last = nums[i][index[i]++];
while (index[i] < nums[i].size() && nums[i][index[i]] == last) index[i]++;
if (index[i] < nums[i].size()) m[nums[i][index[i]]].push(i);
else if (rmin == INT_MAX) rmin = nums[i].back();
}
return range;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.