35ms C++ solution beats than 99% submissions


  • 0
    H

    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;
        }
    };
    

Log in to reply
 

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