C++ with BST


  • 0
    M
    
    class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            if(nums.size()==0)
            {
                return {};
            }
    
            multimap<int, pair<int, int>> map;
            int n = nums.size();
            for(int i=0; i<n; i++)
            {
                map.emplace(nums[i][0], pair<int, int>(i, 0));
            }
    
            if(map.size()==0)
            {
                return {};
            }
    
            vector<int> result = {0, INT_MAX};
            while(1)
            {
                auto first = *(map.begin());
                auto second = *(--map.end());
    
                if( second.first - first.first < result[1] - result[0])
                {
                    result[0] = first.first;
                    result[1] = second.first;
                }
    
                first.second.second++;
                if(first.second.second == nums[first.second.first].size())
                {
                    break;
                }
    
                map.erase(map.begin());
                map.emplace(nums[first.second.first][first.second.second],  pair<int, int>(first.second.first, first.second.second));
            }
    
            return result;
        }
    };
    
    

Log in to reply
 

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