Share my 70ms C++ solution


  • 0
    W

    Basic idea is to find the heaters in front and after the house, and get the radius. Because the heaters and houses are sorted, only one pass is needed.

    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            sort(houses.begin(), houses.end());
            sort(heaters.begin(), heaters.end());
            int i=0, j=0, n=houses.size(), m=heaters.size();
            int res=INT_MIN, cur;
            while (i<n){
                while (j<m && heaters[j]<houses[i]) j++;
                if (j==0) cur = heaters[j]-houses[i];
                else if (j>0 &&j<m) cur = min(heaters[j]-houses[i], houses[i]-heaters[j-1]);
                else cur = houses[i]-heaters[j-1];
                res = max(cur, res);
                i++;
            }
            return res;
        }
    };
    

Log in to reply
 

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