Leetcode•Aug 17, 2025
Heaters
Hazrat Ali
Leetcode
Every house can be warmed, as long as the house is within the heater's warm radius range.
Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.
Notice that all the heaters follow your radius standard, and the warm radius will be the same.
Example 1:
Input: houses = [1,2,3], heaters = [2] Output: 1 Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: houses = [1,2,3,4], heaters = [1,4] Output: 1 Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.
Example 3:
Input: houses = [1,5], heaters = [2] Output: 3
Solution
/**
* @param {number[]} houses
* @param {number[]} heaters
* @return {number}
*
* Time complexity: max(O(nlogn), O(mlogn)) - m is the length of houses, n is the length of heaters.
*/
const findRadius = (houses, heaters) => {
heaters.sort((a, b) => a - b);
let result = -Infinity;
for (let house of houses) {
let index = searchInsert(heaters, house);
const dist1 = index > 0 ? house - heaters[index - 1] : Infinity;
const dist2 = index < heaters.length ? heaters[index] - house : Infinity;
result = Math.max(result, Math.min(dist1, dist2));
}
return result;
};
const searchInsert = (nums, target) => {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] === target) {
return mid;
}
if (target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
};