Heaters
Medium · Two Pointers · Explanation and code example
Sorted Houses and a Monotone Heater Pointer
How it works
As houses advance in sorted order, their nearest heater never moves backward in sorted heater order. Move the heater pointer while the next heater is closer, measure the chosen distance, and take the maximum nearest-heater distance across all houses.
Steps
- Sort houses and heaters.
- For each house, advance the heater pointer while the next heater is closer.
- Track the maximum nearest-heater distance.
Complexity
- Time: O(h log h + t log t + h + t), for h houses and t heaters.
- Space: Python O(h + t) worst-case sorting workspace; C++ O(log h + log t) sorting stack.
Things to watch for
- One heater may cover houses on both sides.
- Tied heater distances can choose either heater.
- Sorting changes both input arrays.
Python code example
class Solution:
def findRadius(self, houses: list[int], heaters: list[int]) -> int:
houses.sort()
heaters.sort()
radius, index = 0, 0
for house in houses:
while index + 1 < len(heaters) and house - heaters[index] > heaters[index + 1] - house:
index += 1
radius = max(radius, abs(house - heaters[index]))
return radius
C++ code example
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
ranges::sort(houses);
ranges::sort(heaters);
int ans = 0;
int i = 0; // heaters' index (currently used)
for (const int house : houses) {
while (i + 1 < heaters.size() &&
house - heaters[i] > heaters[i + 1] - house)
++i; // The next heater is better.
ans = max(ans, abs(heaters[i] - house));
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.