# Heaters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/heaters)
Canonical: https://scaleengineer.com/dsa/problems/heaters
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Nutanix](https://scaleengineer.com/companies/nutanix), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Anduril](https://scaleengineer.com/companies/anduril)
---
## 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.

**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

**Constraints:**

* `1 <= houses.length, heaters.length <= 3 * 104`
* `1 <= houses[i], heaters[i] <= 109`

# Approaches
## Brute Force
This approach iterates through each house and, for every house, finds the minimum distance to any of the heaters by checking all of them. The final answer is the maximum of these minimum distances found for each house.
**Time:** O(N * M), where N is the number of houses and M is the number of heaters. This is because for each of the N houses, we iterate through all M heaters. · **Space:** O(1), as we only use a few variables to store intermediate results, regardless of the input size.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs due to its quadratic time complexity.
### Explanation
The brute-force method is the most straightforward way to solve the problem. The logic is to simulate the process directly. For every single house, we need to find which heater is closest to it. To do this, we can compare its position with every heater's position, calculate the distance, and keep track of the minimum one. After finding the minimum distance for a house, we know that the final radius must be at least this large to cover it. We repeat this for all houses and take the maximum of all these minimum distances, as this maximum value will be the smallest radius that is guaranteed to cover every house.

```java
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int maxRadius = 0;
        for (int house : houses) {
            int minDistance = Integer.MAX_VALUE;
            for (int heater : heaters) {
                minDistance = Math.min(minDistance, Math.abs(house - heater));
            }
            maxRadius = Math.max(maxRadius, minDistance);
        }
        return maxRadius;
    }
}
```
### Algorithm
- Initialize a variable `maxRadius` to 0.
- For each `house` in the `houses` array:
  - Initialize `minDistForHouse` to a very large value (infinity).
  - For each `heater` in the `heaters` array:
    - Calculate the absolute difference `dist = |house - heater|`.
    - Update `minDistForHouse = min(minDistForHouse, dist)`.
  - After checking all heaters for the current house, update `maxRadius = max(maxRadius, minDistForHouse)`.
- Return `maxRadius`.

## Sorting Heaters and Using Binary Search
This approach improves upon the brute-force method by first sorting the `heaters` array. Then, for each house, it uses binary search to efficiently find the closest heater(s) instead of performing a linear scan.
**Time:** O(M log M + N log M), where N is the number of houses and M is the number of heaters. O(M log M) for sorting heaters and O(log M) for the binary search for each of the N houses. · **Space:** O(log M) or O(M), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses O(log M) space on average.
**Pros:** Significantly more efficient than the brute-force approach.; Efficient when the number of heaters is large.
**Cons:** Can be slightly less efficient than the two-pointer approach if the number of houses (N) is much larger than the number of heaters (M).
### Explanation
The core idea is that for any house, its closest heater must be one of the two heaters that 'surround' it in the sorted `heaters` array. By sorting the heaters, we can use binary search to find these two surrounding heaters in logarithmic time, which is a significant improvement over the linear scan of the brute-force approach. For each house, we find its potential position in the sorted `heaters` array. If the house position matches a heater's position, the distance is 0. Otherwise, we identify the heaters immediately to the left and right of the house's position and calculate the distance to each. The smaller of these two distances is the minimum required radius for that house. The final answer is the maximum of these minimum radii over all houses.

```java
import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int result = 0;

        for (int house : houses) {
            int index = Arrays.binarySearch(heaters, house);
            
            // If house is at a heater location, distance is 0 for this house
            if (index >= 0) {
                continue;
            }

            // Find insertion point to locate surrounding heaters
            int insertionPoint = -(index + 1);
            
            int dist1 = Integer.MAX_VALUE;
            // Distance to the heater on the left
            if (insertionPoint > 0) {
                dist1 = house - heaters[insertionPoint - 1];
            }

            int dist2 = Integer.MAX_VALUE;
            // Distance to the heater on the right
            if (insertionPoint < heaters.length) {
                dist2 = heaters[insertionPoint] - house;
            }
            
            result = Math.max(result, Math.min(dist1, dist2));
        }
        return result;
    }
}
```
### Algorithm
- Sort the `heaters` array. This allows for efficient searching.
- Initialize `maxRadius` to 0.
- For each `house` in the `houses` array:
  - Use binary search (e.g., `Arrays.binarySearch`) to find the insertion point of the `house` in the sorted `heaters` array.
  - The insertion point helps identify the two heaters closest to the current house: one to its left (`heaters[insertion_point - 1]`) and one to its right (`heaters[insertion_point]`).
  - Calculate the distance to both these heaters. Handle edge cases where the house is before the first heater or after the last one.
  - The minimum distance for the current house is the smaller of these two distances.
  - Update `maxRadius` with the maximum distance found so far.
- Return `maxRadius`.

## Sorting Both Arrays and Using Two Pointers
This is a highly efficient approach that involves sorting both the `houses` and `heaters` arrays and then using a two-pointer technique to find the minimum radius in a single pass over the sorted arrays.
**Time:** O(N log N + M log M), dominated by the sorting of the two arrays. The subsequent two-pointer scan is O(N + M), which is faster than the main sorting step. · **Space:** O(log N + log M) or O(N + M), depending on the space used by the sorting algorithm.
**Pros:** Very efficient, typically the fastest approach in practice due to the linear scan after sorting.; Optimal time complexity for a comparison-based solution.
**Cons:** Requires modifying the input arrays by sorting them, or creating sorted copies which would increase space complexity.
### Explanation
By sorting both arrays, we can process houses in increasing order of their position. This allows us to find the closest heater for each house without re-scanning the `heaters` array. We use one pointer for houses (`i`) and one for heaters (`j`). As we iterate through the sorted houses, we only need to advance the heater pointer `j` forward. This is because for the next house `houses[i+1]`, its closest heater cannot be before the closest heater of `houses[i]`. For each house, we find the two heaters that bracket it, calculate the distance to both, and take the minimum. The final answer is the maximum of these minimums. This avoids the repeated logarithmic searches of the previous approach, replacing it with a single linear scan.

```java
import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int i = 0; // pointer for houses
        int j = 0; // pointer for heaters
        int radius = 0;

        while (i < houses.length) {
            // Find the heater that is just left of or at the current house's position
            while (j + 1 < heaters.length && heaters[j + 1] <= houses[i]) {
                j++;
            }

            // Distance to the heater on the left (or at the same position)
            int dist1 = Math.abs(houses[i] - heaters[j]);
            
            // Distance to the heater on the right
            int dist2 = Integer.MAX_VALUE;
            if (j + 1 < heaters.length) {
                dist2 = heaters[j + 1] - houses[i];
            }
            
            // The required radius for this house is the minimum of the two distances
            int currentRadius = Math.min(dist1, dist2);
            
            // The overall radius must be large enough for all houses
            radius = Math.max(radius, currentRadius);
            
            i++;
        }
        return radius;
    }
}
```
### Algorithm
- Sort both the `houses` and `heaters` arrays.
- Initialize `radius = 0`, and two pointers, `i = 0` for houses and `j = 0` for heaters.
- Iterate through each `house` using pointer `i`:
  - For the current `house[i]`, find the pair of heaters that surround it. Advance the heater pointer `j` as long as the next heater `heaters[j+1]` is closer to or at the same location as `house[i]`.
  - After finding the best `j`, the closest heaters are `heaters[j]` and `heaters[j+1]` (if it exists).
  - Calculate the distance to the left heater (`dist1 = |houses[i] - heaters[j]|`) and the right heater (`dist2`, if `heaters[j+1]` exists).
  - The minimum radius needed for `house[i]` is `min(dist1, dist2)`.
  - Update the overall `radius` to be the maximum of what's needed for all houses seen so far.
- Return `radius`.

# Solutions
### Java

```java
class Solution {
public
  int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(heaters);
    int res = 0;
    for (int x : houses) {
      int i = Arrays.binarySearch(heaters, x);
      if (i < 0) {
        i = ~i;
      }
      int dis1 = i > 0 ? x - heaters[i - 1] : Integer.MAX_VALUE;
      int dis2 = i < heaters.length ? heaters[i] - x : Integer.MAX_VALUE;
      res = Math.max(res, Math.min(dis1, dis2));
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findRadius(vector<int> &houses, vector<int> &heaters) {
    sort(houses.begin(), houses.end());
    sort(heaters.begin(), heaters.end());
    int left = 0, right = 1e9;
    while (left < right) {
      int mid = left + right >> 1;
      if (check(houses, heaters, mid))
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
  bool check(vector<int> &houses, vector<int> &heaters, int r) {
    int m = houses.size(), n = heaters.size();
    int i = 0, j = 0;
    while (i < m) {
      if (j >= n)
        return false;
      int mi = heaters[j] - r;
      int mx = heaters[j] + r;
      if (houses[i] < mi)
        return false;
      if (houses[i] > mx)
        ++j;
      else
        ++i;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int: houses . sort() heaters . sort() def check(r): m, n = len(houses), len(heaters) i = j = 0 while i < m: if j >= n: return False mi = heaters[j] - r mx = heaters[j] + r if houses[i] < mi: return False if houses[i] > mx: j += 1 else: i += 1 return True left, right = 0, int(1e9) while left < right: mid = (left + right) >> 1 if check(mid): right = mid else: left = mid + 1 return left

```