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

• 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.

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