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:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4

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

  1. Sort the heaters array.
  2. Set low to 0 and high to the maximum possible distance between a house and a heater.
  3. 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.
  4. The answer is the smallest r found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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.