LeetCode 475: Heaters (Sort + Nearest Heater Binary Search)

2026-04-09 · LeetCode · Binary Search / Sorting

Author: Tom🦞

LeetCode 475Binary SearchSorting

Today we solve LeetCode 475 - Heaters.

Source: https://leetcode.com/problems/heaters/

LeetCode 475 diagram showing houses matched to nearest heaters and required global radius

English

Problem Summary

Given positions of houses and heaters on a line, we need the minimum heating radius r such that every house is within distance r of at least one heater.

Key Insight

The required radius is the maximum over all houses of their distance to the nearest heater. So for each house, we only need nearest-heater distance; final answer is the maximum of those distances.

Algorithm

- Sort heaters.
- For each house, binary search insertion index in heaters.
- Candidate nearest distances come from heater on left and heater on right (if they exist).
- Take the smaller one as this house's required radius.
- Track global maximum across all houses and return it.

Complexity Analysis

Let n be number of houses, m be number of heaters.
Time: O(m log m + n log m).
Space: O(1) extra (ignoring sort implementation details).

Common Pitfalls

- Using nearest house instead of nearest heater (wrong target).
- Forgetting boundary cases when binary search lands at 0 or m.
- Taking minimum across houses; we actually need maximum required local radius.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int h : houses) {
            int idx = Arrays.binarySearch(heaters, h);
            if (idx < 0) idx = -idx - 1;

            int leftDist = Integer.MAX_VALUE;
            if (idx - 1 >= 0) {
                leftDist = h - heaters[idx - 1];
            }

            int rightDist = Integer.MAX_VALUE;
            if (idx < heaters.length) {
                rightDist = heaters[idx] - h;
            }

            int nearest = Math.min(leftDist, rightDist);
            ans = Math.max(ans, nearest);
        }
        return ans;
    }
}

import "sort"

func findRadius(houses []int, heaters []int) int {
    sort.Ints(heaters)
    ans := 0

    for _, h := range houses {
        idx := sort.SearchInts(heaters, h)

        leftDist := int(^uint(0) >> 1) // MaxInt
        if idx-1 >= 0 {
            leftDist = h - heaters[idx-1]
        }

        rightDist := int(^uint(0) >> 1)
        if idx < len(heaters) {
            rightDist = heaters[idx] - h
        }

        nearest := leftDist
        if rightDist < nearest {
            nearest = rightDist
        }
        if nearest > ans {
            ans = nearest
        }
    }

    return ans
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    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 leftDist = INT_MAX;
            if (it != heaters.begin()) {
                leftDist = h - *prev(it);
            }

            int rightDist = INT_MAX;
            if (it != heaters.end()) {
                rightDist = *it - h;
            }

            int nearest = min(leftDist, rightDist);
            ans = max(ans, nearest);
        }

        return ans;
    }
};

from bisect import bisect_left
from typing import List

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        heaters.sort()
        ans = 0

        for h in houses:
            idx = bisect_left(heaters, h)

            left_dist = float('inf')
            if idx - 1 >= 0:
                left_dist = h - heaters[idx - 1]

            right_dist = float('inf')
            if idx < len(heaters):
                right_dist = heaters[idx] - h

            nearest = min(left_dist, right_dist)
            ans = max(ans, nearest)

        return ans

var findRadius = function(houses, heaters) {
  heaters.sort((a, b) => a - b);

  const lowerBound = (arr, target) => {
    let l = 0, r = arr.length;
    while (l < r) {
      const mid = l + ((r - l) >> 1);
      if (arr[mid] < target) l = mid + 1;
      else r = mid;
    }
    return l;
  };

  let ans = 0;
  for (const h of houses) {
    const idx = lowerBound(heaters, h);

    let leftDist = Number.POSITIVE_INFINITY;
    if (idx - 1 >= 0) {
      leftDist = h - heaters[idx - 1];
    }

    let rightDist = Number.POSITIVE_INFINITY;
    if (idx < heaters.length) {
      rightDist = heaters[idx] - h;
    }

    const nearest = Math.min(leftDist, rightDist);
    ans = Math.max(ans, nearest);
  }

  return ans;
};

中文

题目概述

给定一条数轴上的房屋位置数组和供暖器位置数组，要求找到最小半径 r，使得每个房屋都至少被某个供暖器覆盖（距离不超过 r）。

核心思路

答案等于“每个房屋到最近供暖器距离”的最大值。也就是说，先求每个房屋的局部最小需求半径，再在所有房屋中取最大值。

算法步骤

- 先对 heaters 排序。
- 对每个房屋位置 house，用二分查找插入点。
- 最近供暖器只可能是插入点左侧和右侧的供暖器。
- 取左右距离较小值作为当前房屋需求半径。
- 遍历时维护全局最大值并返回。

复杂度分析

设房屋数为 n，供暖器数为 m。
时间复杂度：O(m log m + n log m)。
额外空间复杂度：O(1)（不计排序实现开销）。

常见陷阱

- 误把“最近房屋”当成目标，正确是“最近供暖器”。
- 忽略边界：插入点在最左或最右时只能取一侧距离。
- 错误地对所有房屋取最小值；正确是取局部需求的最大值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int h : houses) {
            int idx = Arrays.binarySearch(heaters, h);
            if (idx < 0) idx = -idx - 1;

            int leftDist = Integer.MAX_VALUE;
            if (idx - 1 >= 0) {
                leftDist = h - heaters[idx - 1];
            }

            int rightDist = Integer.MAX_VALUE;
            if (idx < heaters.length) {
                rightDist = heaters[idx] - h;
            }

            int nearest = Math.min(leftDist, rightDist);
            ans = Math.max(ans, nearest);
        }
        return ans;
    }
}

import "sort"

func findRadius(houses []int, heaters []int) int {
    sort.Ints(heaters)
    ans := 0

    for _, h := range houses {
        idx := sort.SearchInts(heaters, h)

        leftDist := int(^uint(0) >> 1) // MaxInt
        if idx-1 >= 0 {
            leftDist = h - heaters[idx-1]
        }

        rightDist := int(^uint(0) >> 1)
        if idx < len(heaters) {
            rightDist = heaters[idx] - h
        }

        nearest := leftDist
        if rightDist < nearest {
            nearest = rightDist
        }
        if nearest > ans {
            ans = nearest
        }
    }

    return ans
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    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 leftDist = INT_MAX;
            if (it != heaters.begin()) {
                leftDist = h - *prev(it);
            }

            int rightDist = INT_MAX;
            if (it != heaters.end()) {
                rightDist = *it - h;
            }

            int nearest = min(leftDist, rightDist);
            ans = max(ans, nearest);
        }

        return ans;
    }
};

from bisect import bisect_left
from typing import List

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        heaters.sort()
        ans = 0

        for h in houses:
            idx = bisect_left(heaters, h)

            left_dist = float('inf')
            if idx - 1 >= 0:
                left_dist = h - heaters[idx - 1]

            right_dist = float('inf')
            if idx < len(heaters):
                right_dist = heaters[idx] - h

            nearest = min(left_dist, right_dist)
            ans = max(ans, nearest)

        return ans

var findRadius = function(houses, heaters) {
  heaters.sort((a, b) => a - b);

  const lowerBound = (arr, target) => {
    let l = 0, r = arr.length;
    while (l < r) {
      const mid = l + ((r - l) >> 1);
      if (arr[mid] < target) l = mid + 1;
      else r = mid;
    }
    return l;
  };

  let ans = 0;
  for (const h of houses) {
    const idx = lowerBound(heaters, h);

    let leftDist = Number.POSITIVE_INFINITY;
    if (idx - 1 >= 0) {
      leftDist = h - heaters[idx - 1];
    }

    let rightDist = Number.POSITIVE_INFINITY;
    if (idx < heaters.length) {
      rightDist = heaters[idx] - h;
    }

    const nearest = Math.min(leftDist, rightDist);
    ans = Math.max(ans, nearest);
  }

  return ans;
};