Problem Explanation

You are given a list of houses and a list of heaters. The houses and heaters are represented by their positions on a line. You need to find the minimum distance or radius of the heaters such that all the houses are covered by the heaters. The radius of a heater is the distance a heater can cover to its left or right.

A house is considered to be within the range of a heater if its distance to that heater is less than or equal to the heater's radius. All heaters have the same radius.

Example

Consider an example where the houses are located at [1,2,3,4] and the heaters are located at [1,4].

First, sort both the houses and heaters list in ascending order.

Houses: [1,2,3,4]

Heaters: [1,4]

For a heater at position 1, the houses that are in its range will be [1,2] if its radius is 1 and for heater at position 4, the houses that are in its range will be [3,4] if its radius is also 1.

Thus, the minimum heater radius that will cover all houses is 1.

Approach

The algorithm takes the following approach to solve the problem.

1. Sort the array of houses and heaters in ascending order.
2. Traverse through the houses array and for each house, calculate the minimum distance to the nearest heater.
3. The maximum of these distances will be the required answer.

Python Solution

1
2python
3class Solution: 
4    def findRadius(self, houses: List[int], heaters: List[int]) -> int: 
5        houses.sort() 
6        heaters.sort() 
7        heaters=[float('-inf')]+heaters+[float('inf')] 
8        ans,i = 0,0 
9        for house in houses: 
10            while house > heaters[i]: 
11                i += 1 
12            dist = min(heaters[i] - house, house - heaters[i - 1]) 
13            ans = max(ans, dist) 
14        return ans 

Java Solution

1
2java
3class Solution {
4    public int findRadius(int[] houses, int[] heaters) {
5        Arrays.sort(houses);
6        Arrays.sort(heaters);
7        int i = 0, res = 0;
8        for (int house : houses) {
9            while (i + 1 < heaters.length && heaters[i] + heaters[i + 1] <= house * 2) i++;
10            res = Math.max(res, Math.abs(heaters[i] - house));
11        }
12        return res;
13    }
14}

JavaScript Solution

1
2javascript
3var findRadius = function(houses, heaters) {
4    heaters.sort((a, b) => a - b);
5    return Math.max(...houses.map(house => {
6        let index = bisect(heaters, house);
7        let left = heaters[index - 1];
8        let right = heaters[index];
9        return Math.min(Math.abs(house - left) || Infinity, Math.abs(house - right) || Infinity);
10    }));
11};
12function bisect(arr, x) {
13    let left = 0, right = arr.length;
14    while (left < right) {
15        let mid = Math.trunc(left + (right - left) / 2);
16        if (x > arr[mid]) left = mid + 1;
17        else right = mid;
18    }
19    return left;
20}

C++ Solution

1
2c++
3class Solution {
4public:
5    int findRadius(vector<int>& houses, vector<int>& heaters) {
6        sort(houses.begin(), houses.end());
7        sort(heaters.begin(), heaters.end());
8        vector<int> res(houses.size(), INT_MAX);
9        for (int i = 0, j = 0; i < houses.size();) {
10            if (heaters[j] >= houses[i]) {
11                res[i] = heaters[j] - houses[i];
12                i++;
13            } else if (j < heaters.size() - 1) {
14                j++;
15            } else {
16                return max(res[i - 1], res[i]);
17            }
18        }
19        return *max_element(res.begin(), res.end());
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public int FindRadius(int[] houses, int[] heaters) {
5        Array.Sort(houses);
6        Array.Sort(heaters);
7        int i = 0, res = 0;
8        foreach(int house in houses){
9            while(i < heaters.Length - 1 && heaters[i] + heaters[i + 1] <= house * 2){
10                i++;
11            }
12            res = Math.Max(res, Math.Abs(heaters[i] - house));
13        }
14        return res;
15    }
16}

This solution works by calculating the closest heater for each house and the maximum distance from a house to its closest heater would be the answer as all houses can be warmed up by using radius equal to the maximum distance calculated.# R Solution

To solve this problem in R, we can organize the solution code into a function named findRadius(houses, heaters), where houses and heaters are vectors.

1
2r
3findRadius <- function(houses, heaters) {
4  houses <- sort(houses)
5  heaters <- sort(c(-Inf, heaters, Inf))
6  res <- i <- 0
7  for (house in houses) {
8    while (house > heaters[i+2]) i <- i + 1
9    res <- max(res, min(abs(house-heaters[(i+1):(i+2)])))
10  }
11  return(res)
12}

This R function uses a for-loop to iterate through each element in the sorted houses and heaters vectors. For each house, it finds the closest heater and measures the distance, then updates the maximum distance res if needed. At the end, the function returns res, indicating the minimum radius of the heaters so that all houses are covered.

The SQL Solution

If the houses and heaters are stored in a SQL database, the same problem can be solved using an SQL query. For simplicity, let's assume that there are two tables - houses and heaters, each with a single column position.

1
2sql
3SELECT MAX(MIN(ABS(house.position - heater.position)))
4FROM houses AS house, heaters AS heater
5GROUP BY heater.position;

This query calculates the distance from each heater to all houses, then find the maximum one among the minimized distances. This query assumes that the heaters' radius can vary. To find the minimum common radius for all heaters, we wrap the previous query with another MAX function:

1
2sql
3SELECT MAX(distance)
4FROM (
5  SELECT heaters.position, MIN(ABS(houses.position - heaters.position)) AS distance
6  FROM houses
7  JOIN heaters ON houses.position <= heaters.position
8  GROUP BY heaters.position
9) AS subquery;

This SQL query returns the same result as the Python, Java, JavaScript, C++, and C# solutions described above.