C++ solution using Set with explanation


  • 0
    A

    The idea is to maintain an ordered set that contains an element of each row (represents your active interval). Then, try to look for a smaller interval by replacing the minimum element at active.begin() with the next element of the same row where the element is popped. Lastly, calculate the difference between left and right interval and exit the loop once the algorithm reaches the end of one of its vectors.

    Solution Inspired by @tmt514

    class Solution{
    public:
       vector<int> smallestRange(vector<vector<int>>& nums) {
         
           set<pair<int,int> > active; 
           int diff,l,r; 
           for(int i=0 ; i< nums.size() ; ++i)
           		active.insert(make_pair(nums[i][0], i));
    
           	l = active.begin()->first; r = active.rbegin()->first; 
           	diff = r-l;
    
           	while(active.begin()->first != nums[active.begin()->second].back())
           	{
           		int val = active.begin()->first;
           		int row = active.begin()->second;
           		active.erase(active.begin());
    
           		active.insert({ *upper_bound(nums[row].begin(), nums[row].end(), val), row});
    
           		if(active.rbegin()->first - active.begin()->first < diff)
           		{
           			diff = active.rbegin()->first-active.begin()->first; 
           			l = active.begin()->first;  r = active.rbegin()->first;
           		}
           	}
           	return {l,r};
        }
    };
    

Log in to reply
 

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