Heaters — Minimum Radius to Warm All Houses

Problem Statement

Winter is coming! You are given the positions of houses and heaters on a horizontal line. Each heater has the same radius r, and warms all houses within distance r.

Find the minimum radius so that every house is covered by at least one heater.

Constraints

• 1 <= houses.length, heaters.length <= 3 * 10^4
• 1 <= houses[i], heaters[i] <= 10^9
• Positions can be unsorted

Example

Input: houses = [1, 2, 3, 4], heaters = [1, 4]

Output: 1

Explanation: With radius 1, heater at 1 covers houses 1,2 and heater at 4 covers houses 3,4.

Input: houses = [1, 5], heaters = [2]

Output: 3

Explanation: Heater at 2 needs radius 3 to reach house 5.

What the Interviewer Expects

1. Don't over-think it as a graph — a common trap. This is purely a binary search / sorting problem.
2. Sort both arrays.
3. For each house, find the closest heater — the required radius for that house is the distance to its nearest heater.
4. Answer = max of all these minimum distances — the largest gap any house has to its closest heater.
5. Two approaches:
   • For each house, binary search the nearest heater in the sorted heater array. O(n log m).
   • Two pointers after sorting. O(n + m).

Follow-ups

1. What if heaters can have different radii and you want to minimize total cost?
2. What if houses and heaters are in 2D space instead of a line?
3. Can you solve it with two pointers instead of binary search? What's the complexity difference?
4. What if you could add ONE more heater anywhere — where would you place it to minimize the radius?