C++ clean solution with explanation


  • 14

    Sorting is O(n log n). The rest is O(n).
    Here, A = houses and H = heaters.

    class Solution {
    public:
    /*
    Example:    h = house,  * = heater  M = INT_MAX
    
            h   h   h   h   h   h   h   h   h    houses
            1   2   3   4   5   6   7   8   9    index
            *           *       *                heaters
                    
            0   2   1   0   1   0   -   -   -    (distance to nearest RHS heater)
            0   1   2   0   1   0   1   2   3    (distance to nearest LHS heater)
    
            0   1   1   0   1   0   1   2   3    (res = minimum of above two)
    
    Result is maximum value in res, which is 3.
    */
        int findRadius(vector<int>& A, vector<int>& H) {
            sort(A.begin(), A.end());
            sort(H.begin(), H.end());
            vector<int> res(A.size(), INT_MAX); 
            
            // For each house, calculate distance to nearest RHS heater
            for (int i = 0, h = 0; i < A.size() && h < H.size(); ) {
                if (A[i] <= H[h]) { res[i] = H[h] - A[i]; i++; }
                else { h++; }
            }
            
            // For each house, calculate distance to nearest LHS heater
            for (int i = A.size()-1, h = H.size()-1; i >= 0 && h >= 0; ) {
                if (A[i] >= H[h]) { res[i] = min(res[i], A[i] - H[h]); i--; }
                else { h--; }
            }
           
            return *max_element(res.begin(), res.end());
        }
    };
    

  • 1
    C

    Hi, thanks a lot for this example and explanation, could not get my head around other solutions but this one was crystal clear to me :)


Log in to reply
 

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