76ms C++ solution with O(1) space


  • 0
    W

    I use three pointers: two of them point at houses and heaters; the third one points at the middle position of two neighbor heaters.

    class Solution {
        public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            int res = 0;
            // Sorting first
            sort(houses.begin(), houses.end());
            sort(heaters.begin(),heaters.end());
            // Sizes
            int s1 = houses.size();
            int s2 = heaters.size(); 
           // This is the position of the middle point of two neighbor heaters
            double mid = 0;   
           // If house[i] < mid, the house[i] is at the left of "mid"
           // "mid" helps determine which heater the house is close to
    
            int j = -1;      // Index of heater
            int i = 0;       // Index of house
    
            while (i<s1) {
                 // If the house is at the right side of "mid", we need to update "mid" and compare them again
                if (double(houses[i])>=mid) {
                    ++j;
                    if (j<s2-1)
                        mid = double(heaters[j] + heaters[j+1]) / 2;
                    else {
                        // If this is the last heater, we can set the "mid" to the right side of the last house
                        mid = houses[s1-1] + 1;
                    }
                    continue;  // Compare them again
                }
                res = max(res, abs(heaters[j]-houses[i]));
                ++i;
            }
            return res;
        }
    };
    

    Hope this helps.


Log in to reply
 

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