# C++ clean solution with explanation

• 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());
}
};
``````

• 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 :)

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