C++ Solution with Explanations


  • 0
    P
    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            // Key: the global minimum radius is actually the maximum value of all the local minimums (local: for each house location)
            if (heaters.empty()) {
                return INT_MAX;
            }
            
            int globalMinRadius = INT_MIN;
            int localMinRadius;
            sort(heaters.begin(), heaters.end());
            
            for (int index : houses) {
                auto it = lower_bound(heaters.begin(), heaters.end(), index);
                if (it == heaters.end()) {
                    // Find the position of the house relative to the heaters
                    // If not found, it means that the house is positioned either before the first heater or after the last heater
                    localMinRadius = (index < *(heaters.begin()) ? abs(*(heaters.begin()) - index) 
                                                                : abs(*(heaters.end() - 1) - index));
                } else {
                    // If found
                    // It can be on the first heater, on the last heater, or somewhere in the middle. In the last case it can be on a heater, between a heater and its previous one, or between a heater and its next one
                   // For first two cases, substitute the distance to the previous or to the next with INT_MAX
                   // For the third case, compute local minimum by comparing the three distances, from the previous, from the current, and from the next
                    localMinRadius = min(abs(*it - index), 
                                         min((it != heaters.end() - 1) ? abs(*(it + 1) - index) : INT_MAX, 
                                             (it != heaters.begin()) ? abs(*(it - 1) - index) : INT_MAX));
                }
                globalMinRadius = max(globalMinRadius, localMinRadius);
            }
            
            return globalMinRadius;
        }
    };
    

Log in to reply
 

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