Heaters
Asked at Anduril
Problem
Heaters gives you house positions and heater positions on a line and asks for the minimum radius such that every house is within that radius of some heater. The answer is simply the largest "distance to nearest heater" over all houses — the work is finding each nearest heater efficiently.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Reframe it: a radius works iff every house is within it of its nearest heater. So the answer is max over houses of (distance to nearest heater).
Brute force compares every house with every heater: O(n * m).
Key insight: sort the heaters. For each house, binary search for the first heater at or after it; the nearest heater is either that one or the one just before it.
Walkthrough: houses [1,2,3,4], heaters [1,4]. House 1 -> 0, house 2 -> min(1, 2) = 1, house 3 -> min(2, 1) = 1, house 4 -> 0. Answer 1.
Alternative: sort both arrays and sweep a pointer over heaters that only moves forward — O(n log n + m log m) with an O(n + m) sweep.
Optimal Approach
Step 1: Sort heaters.
Step 2: For each house h:
i = lower_bound(heaters, h) (first heater >= h).
right = heaters[i] - h if i < m, else infinity.
left = h - heaters[i-1] if i > 0, else infinity.
radius = max(radius, min(left, right)).
Step 3: Return radius.
Time: O((n + m) log m). Space: O(1) beyond sorting.
What Trips People Up in Real Interviews
Binary searching on the radius. It works (O(log range * ...)), but the nearest-heater observation is simpler and faster.
Only checking the heater at or after the house. The heater just before it may be closer.
Forgetting to sort the heaters — the input is not guaranteed sorted.
Index errors at the boundaries when the house is before the first heater or after the last.
Solution Code
from bisect import bisect_left
def findRadius(houses, heaters):
heaters.sort()
radius = 0
for h in houses:
i = bisect_left(heaters, h)
right = heaters[i] - h if i < len(heaters) else float('inf')
left = h - heaters[i - 1] if i > 0 else float('inf')
radius = max(radius, min(left, right))
return radiusFrequently Asked Questions
What is the Heaters problem?
Heaters gives you house positions and heater positions on a line and asks for the minimum radius such that every house is within that radius of some heater. The answer is simply the largest "distance to nearest heater" over all houses — the work is finding each nearest heater efficiently.
How do you solve Heaters?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Heaters?
Heaters is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Heaters?
- Binary searching on the radius. It works (`O(log range * ...)`), but the nearest-heater observation is simpler and faster.
- Only checking the heater at or after the house. The heater just before it may be closer.
- Forgetting to sort the heaters — the input is not guaranteed sorted.
- Index errors at the boundaries when the house is before the first heater or after the last.