# 5-line solution directly using std::lower_bound for binary search (detailed explanation with picture illustration)

• Key observation: Each house should be covered by its nearest heater. The nearest heater to a house is either next right to it or next left to it, whichever is closer.

Algorithm:

1. Sort heaters `vector<int> hts` by positions (O(NheaterlogNheater));
2. For each house `h`, use `std::lower_bound` to find the nearest heater and update the overall min heater radius (O(logNheater) for each house). Note
• Next right heater position: `i = lower_bound(hts.begin(), hts.end(), h)`.
• Next left heater position: `--i` for the iterator above .

The overall time complexity is O((Nhouse+Nheater)logNheater).

``````    int findRadius(vector<int>& houses, vector<int>& hts) {
sort(hts.begin(), hts.end()); int res = 0;
for (int h:houses) { // find nearest distance to heaters
auto i = lower_bound(hts.begin(), hts.end(), h); // next right heater
res = max(res, min(i!=hts.begin()? h-*(--i):INT_MAX, i!=hts.end()? *i - h:INT_MAX));
}
return res;
}
``````

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