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

  • 0

    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 {
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            int res = 0;
            // Sorting first
            sort(houses.begin(), houses.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) {
                    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]));
            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.