Heaters

medium array binary search sorting two pointers

Problem

Houses and heaters sit on a number line. Every heater has the same radius r and warms houses within distance r of itself. Return the minimum radius needed so that all houses are warmed.

Inputhouses = [1, 2, 3, 4], heaters = [1, 4]

Output1

House 2 → distance to nearest heater 1 is 1; house 3 → distance 1. Max nearest-distance = 1.

houses

heaters

def find_radius(houses, heaters):
    heaters.sort()
    from bisect import bisect_left
    ans = 0
    for h in houses:
        i = bisect_left(heaters, h)
        left = heaters[i - 1] if i > 0 else float('-inf')
        right = heaters[i] if i < len(heaters) else float('inf')
        ans = max(ans, min(h - left, right - h))
    return ans

function findRadius(houses, heaters) {
  heaters.sort((a, b) => a - b);
  let ans = 0;
  for (const h of houses) {
    let lo = 0, hi = heaters.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (heaters[m] < h) lo = m + 1;
      else hi = m;
    }
    const left = lo > 0 ? h - heaters[lo - 1] : Infinity;
    const right = lo < heaters.length ? heaters[lo] - h : Infinity;
    ans = Math.max(ans, Math.min(left, right));
  }
  return ans;
}

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int h : houses) {
            int i = Arrays.binarySearch(heaters, h);
            if (i < 0) i = -i - 1;
            int left = i > 0 ? h - heaters[i - 1] : Integer.MAX_VALUE;
            int right = i < heaters.length ? heaters[i] - h : Integer.MAX_VALUE;
            ans = Math.max(ans, Math.min(left, right));
        }
        return ans;
    }
}

int findRadius(vector<int>& houses, vector<int>& heaters) {
    sort(heaters.begin(), heaters.end());
    int ans = 0;
    for (int h : houses) {
        auto it = lower_bound(heaters.begin(), heaters.end(), h);
        int right = it == heaters.end() ? INT_MAX : *it - h;
        int left = it == heaters.begin() ? INT_MAX : h - *(it - 1);
        ans = max(ans, min(left, right));
    }
    return ans;
}

Explanation

Every heater shares the same radius, so the radius we need is decided by the worst-off house — the one whose nearest heater is farthest away. The plan is: for each house find its nearest heater, then take the largest of those nearest-distances.

After sorting the heaters, we can find the nearest one for a house with a binary search (bisect_left / lower_bound). It gives the position i where the house would slot in; the nearest heater is then either the one just before (heaters[i-1]) or the one at i (heaters[i]).

We compute min(h - left, right - h) for that house — the distance to whichever heater is closer — and keep a running max across all houses. Edge cases where a house is past one end use infinity so only the real side counts.

Example: houses = [1,2,3,4], heaters = [1,4]. House 2's nearest heater is 1 (distance 1); house 3's nearest is 4 (distance 1); houses 1 and 4 sit on heaters (distance 0). The maximum is 1, so radius 1 covers everyone.

Sorting plus a binary search per house gives O((H + K) log K) overall.

Time: O((H + K) log K) Space: O(1)