AlgoMaster Logo

Heaters

mediumUpdated September 21, 2026

Understanding the Problem

We have a number line with houses and heaters placed at various positions. Every heater uses the same radius, and a house is "warm" if it falls within the radius of at least one heater. We need to find the smallest radius that makes every house warm.

The answer is determined by the house that is hardest to reach. For each house, we find the distance to its closest heater. Since every heater shares the same radius, the radius must be at least as large as that closest distance for the house to be covered. The smallest radius that covers all houses is therefore the maximum, over all houses, of each house's closest-heater distance. Any radius below that maximum leaves at least one house uncovered.

So the problem reduces to: for each house, find its nearest heater, then return the largest of those nearest distances.

Key Constraints:

  • 1 <= houses.length, heaters.length <= 3 * 10^4 → Both arrays can hold up to 30,000 elements. An O(m n) brute force reaches 9 10^8 operations, too slow for typical limits. We want O((m + n) log n) or better.
  • 1 <= houses[i], heaters[i] <= 10^9 → Positions reach 10^9, but distances stay within 10^9 too, so they fit in a 32-bit signed integer (max ~2.1 * 10^9). No overflow concern, and the positions never index an array, so the large range does not affect the approach.

Approach 1: Brute Force

Intuition

For every house, scan all the heaters and compute the distance to each one. The nearest heater for that house is the one with the smallest distance. After computing the nearest-heater distance for every house, the answer is the maximum of those distances.

This is correct but checks every house-heater pair, giving O(m * n) work.

Algorithm

  1. Initialize result = 0.
  2. For each house in houses:
    • Initialize closestDist = infinity.
    • For each heater in heaters:
      • Compute dist = |house - heater|.
      • Update closestDist = min(closestDist, dist).
    • Update result = max(result, closestDist).
  3. Return result.

Visualization and Code

Loading animation...

The scan over every heater is the slow part. Sorting the heaters once lets each house find its nearest heater with a binary search rather than a full scan.

Approach 2: Sort + Binary Search

Intuition

If the heaters are sorted, we can use binary search to find the closest heater to each house in O(log n) time instead of scanning all heaters.

For a given house, binary search finds the position where the house would be inserted into the sorted heaters array. The closest heater must be one of two candidates: the heater just to the left of that insertion point (the largest heater that's <= the house position), or the heater just to the right (the smallest heater that's >= the house position). We check both and take the smaller distance.

Algorithm

  1. Sort the heaters array.
  2. Initialize result = 0.
  3. For each house in houses:
    • Binary search for the house position in the sorted heaters array. Find the index idx where the house would be inserted.
    • Compute leftDist: if idx > 0, the distance to heaters[idx - 1]. Otherwise, infinity.
    • Compute rightDist: if idx < heaters.length, the distance to heaters[idx]. Otherwise, infinity.
    • The closest heater distance for this house is min(leftDist, rightDist).
    • Update result = max(result, min(leftDist, rightDist)).
  4. Return result.

Visualization and Code

Loading animation...

Each house still starts a fresh binary search. Sorting the houses as well removes the need to search at all: as we move to a house further right, its closest heater can only stay put or move right, so a single pointer walking forward through the heaters suffices.

Approach 3: Sort + Two Pointers

Intuition

Sort both arrays and process houses from left to right while maintaining a single pointer into the heaters array. When the next house lies further right, its closest heater is at the same index or further right than the previous house's closest heater, never to the left. The reason: if heater h is the closest to house a, then for any house b >= a, no heater left of h can be strictly closer to b than h is, because moving right from a only increases distance to those left heaters. So the pointer only ever moves forward, and over the whole pass it advances at most n times total.

For each house, advance the heater pointer while the next heater is at least as close to the current house as the current heater. When advancing would no longer reduce the distance, the pointer sits on the closest heater. Record that distance and move to the next house.

Algorithm

  1. Sort both houses and heaters.
  2. Initialize heaterIdx = 0 and result = 0.
  3. For each house in sorted houses:
    • While heaterIdx < heaters.length - 1 and the next heater is at least as close as the current heater, increment heaterIdx.
    • Update result = max(result, |house - heaters[heaterIdx]|).
  4. Return result.

Visualization and Code

Loading animation...