Simple C++ solution taking 72 ms: O(NlogN) sorting + O(N) to find Radius


  • 0
    A

    Simple C++ solution taking 72 ms: O(NlogN) sorting + O(N) to find Radius

    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            int radius=0;
            if(houses.size()==0 || heaters.size() == 0)
              return 0;
              
            sort(houses.begin(),houses.end());
            sort(heaters.begin(), heaters.end());
            
            int left, right, house, heater, j=0;
            
            //For houses < heaters[0], max radius = heaters[0] - houses[0]
            if(houses[0] <= heaters[0])
            {
               radius = heaters[0] - houses[0];
               while(j<houses.size() && houses[j] <= heaters[0])
                j++;
            }
            
            //For heater[i-1] < houses <= heaters[i], find max radius
            for(int i = 1; i< heaters.size() && j<houses.size(); i++)
            {
               left = heaters[i-1];
               right = heaters[i];
               while(j<houses.size() && houses[j] <= right)
               {
                   heater = houses[j];
                   if(min(heater-left, right-heater) > radius)
                    radius = min(heater-left, right-heater);
                   j++;
               }
            }
            
            //For houses > heater[last],  max radius = house[last] - heater[last]
            heater = heaters[heaters.size() - 1];
            house = houses[houses.size() - 1];
            if(j<houses.size() && house > heater)
            {
               if(house - heater > radius)
                radius = house - heater;
            }
            
            return radius;
        }
    };
    

Log in to reply
 

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