475. Heaters
Asked at Anduril
Difficulty
Medium
Time
O((n + m) log m)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given two lists of integer positions on a straight line: houses and heaters. Every heater warms everything within the same fixed distance, called the radius. A house is warm if some heater is at most radius away from it.
Return the smallest radius that warms every house. All heaters must use the same radius, so you cannot give one heater a bigger reach than another.
A useful way to think about it: for each house, look at the closest heater and measure that gap. The answer is the largest of those gaps, because the radius has to be big enough for the worst-placed house.
One radius must cover every house
Constraints
- ●
1 <= houses.length, heaters.length <= 3 * 10^4 - ●
1 <= houses[i], heaters[i] <= 10^9
Examples
houses = [1,2,3], heaters = [2]1houses = [1,2,3,4], heaters = [1,4]1houses = [1,5], heaters = [2]3Asked At
1 companies| 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.
Sort heaters, binary search per house
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
O((n + m) log m) timefrom 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 runs in O((n + m) log m) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.