Heaters Problem
MediumUpdated: Nov 26, 2024
Practice on:
Problem
Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.
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 the same.
Examples
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
Method 1 – Feasibility Check with Binary Search
Intuition
We want to find the minimum radius r such that every house is within r of at least one heater. If we try a value for r, we can check if all houses are covered. If yes, try a smaller r; if not, try a larger r. This is a classic binary search on the answer.
Approach
- Sort the heaters array.
- Set low to 0 and high to the maximum possible distance between a house and a heater.
- Use binary search to find the smallest r such that all houses are covered:
- For each house, check if there is a heater within r distance (use binary search or two pointers).
- If all houses are covered, try a smaller r; else, try a larger r.
- The answer is the smallest r found.
Code
C++
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int l = 0, r = 1e9, ans = r;
while (l <= r) {
int m = l + (r - l) / 2;
bool ok = true;
for (int h : houses) {
auto it = lower_bound(heaters.begin(), heaters.end(), h);
int d1 = it == heaters.end() ? 1e9 : abs(*it - h);
int d2 = it == heaters.begin() ? 1e9 : abs(*prev(it) - h);
if (min(d1, d2) > m) { ok = false; break; }
}
if (ok) { ans = m; r = m - 1; }
else l = m + 1;
}
return ans;
}
};
Go
import "sort"
func findRadius(houses []int, heaters []int) int {
sort.Ints(heaters)
l, r, ans := 0, 1e9, 1e9
for l <= r {
m := l + (r-l)/2
ok := true
for _, h := range houses {
i := sort.SearchInts(heaters, h)
d1 := 1e9
if i < len(heaters) { d1 = abs(heaters[i]-h) }
d2 := 1e9
if i > 0 { d2 = abs(heaters[i-1]-h) }
if min(d1, d2) > m { ok = false; break }
}
if ok { ans = m; r = m-1 } else { l = m+1 }
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if a < b { return a } else { return b } }
Java
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int l = 0, r = (int)1e9, ans = r;
while (l <= r) {
int m = l + (r - l) / 2;
boolean ok = true;
for (int h : houses) {
int i = Arrays.binarySearch(heaters, h);
if (i < 0) i = -i - 1;
int d1 = i < heaters.length ? Math.abs(heaters[i] - h) : (int)1e9;
int d2 = i > 0 ? Math.abs(heaters[i-1] - h) : (int)1e9;
if (Math.min(d1, d2) > m) { ok = false; break; }
}
if (ok) { ans = m; r = m - 1; }
else l = m + 1;
}
return ans;
}
}
Kotlin
class Solution {
fun findRadius(houses: IntArray, heaters: IntArray): Int {
heaters.sort()
var l = 0
var r = 1_000_000_000
var ans = r
while (l <= r) {
val m = l + (r - l) / 2
var ok = true
for (h in houses) {
val i = heaters.binarySearch(h).let { if (it < 0) -it - 1 else it }
val d1 = if (i < heaters.size) Math.abs(heaters[i] - h) else 1_000_000_000
val d2 = if (i > 0) Math.abs(heaters[i-1] - h) else 1_000_000_000
if (minOf(d1, d2) > m) { ok = false; break }
}
if (ok) { ans = m; r = m - 1 }
else l = m + 1
}
return ans
}
}
Python
import bisect
class Solution:
def findRadius(self, houses: list[int], heaters: list[int]) -> int:
heaters.sort()
l, r, ans = 0, int(1e9), int(1e9)
while l <= r:
m = (l + r) // 2
ok = True
for h in houses:
i = bisect.bisect_left(heaters, h)
d1 = abs(heaters[i] - h) if i < len(heaters) else int(1e9)
d2 = abs(heaters[i-1] - h) if i > 0 else int(1e9)
if min(d1, d2) > m:
ok = False
break
if ok:
ans = m
r = m - 1
else:
l = m + 1
return ans
Rust
impl Solution {
pub fn find_radius(houses: Vec<i32>, mut heaters: Vec<i32>) -> i32 {
heaters.sort();
let (mut l, mut r, mut ans) = (0, 1_000_000_000, 1_000_000_000);
while l <= r {
let m = l + (r - l) / 2;
let mut ok = true;
for &h in &houses {
let i = match heaters.binary_search(&h) {
Ok(idx) => idx,
Err(idx) => idx,
};
let d1 = if i < heaters.len() { (heaters[i] - h).abs() } else { 1_000_000_000 };
let d2 = if i > 0 { (heaters[i-1] - h).abs() } else { 1_000_000_000 };
if d1.min(d2) > m { ok = false; break; }
}
if ok { ans = m; r = m - 1; } else { l = m + 1; }
}
ans
}
}
TypeScript
class Solution {
findRadius(houses: number[], heaters: number[]): number {
heaters.sort((a, b) => a - b);
let l = 0, r = 1e9, ans = 1e9;
while (l <= r) {
let m = Math.floor((l + r) / 2), ok = true;
for (let h of houses) {
let i = heaters.findIndex(x => x >= h);
if (i === -1) i = heaters.length;
let d1 = i < heaters.length ? Math.abs(heaters[i] - h) : 1e9;
let d2 = i > 0 ? Math.abs(heaters[i-1] - h) : 1e9;
if (Math.min(d1, d2) > m) { ok = false; break; }
}
if (ok) { ans = m; r = m - 1; }
else l = m + 1;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log m log h), where n is the number of houses, m is the number of heaters, and h is the search range for radius. - 🧺 Space complexity:
O(1), only constant extra space is used.