# LeetCode 475: Heaters

## Problem Restatement

We are given two arrays:

```python
houses
heaters
```

Each value is a position on a horizontal line.

Every heater has the same warm radius `r`.

A heater at position `h` warms every house whose position `x` satisfies:

```python
abs(x - h) <= r
```

We need to return the minimum radius `r` so that every house is covered by at least one heater. The official problem states that all heaters use the same radius, and we need the minimum radius that covers all houses.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `houses`, positions of houses |
| Input | `heaters`, positions of heaters |
| Output | Minimum common heater radius |
| Rule | A house is covered if it lies within radius of any heater |

Function shape:

```python
def findRadius(houses: list[int], heaters: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
houses = [1, 2, 3]
heaters = [2]
```

The heater at `2` covers:

```python
1 with distance 1
2 with distance 0
3 with distance 1
```

So the minimum radius is:

```python
1
```

Example 2:

```python
houses = [1, 2, 3, 4]
heaters = [1, 4]
```

House `2` is distance `1` from heater `1`.

House `3` is distance `1` from heater `4`.

So radius `1` covers all houses.

Answer:

```python
1
```

Example 3:

```python
houses = [1, 5]
heaters = [2]
```

House `1` is distance `1` from heater `2`.

House `5` is distance `3` from heater `2`.

The radius must be at least `3`.

Answer:

```python
3
```

## First Thought: Check Every House Against Every Heater

For each house, we can compute its distance to every heater.

The closest heater determines the radius needed for that house.

Then the answer is the maximum of these closest distances.

```python
class Solution:
    def findRadius(self, houses: list[int], heaters: list[int]) -> int:
        answer = 0

        for house in houses:
            closest = float("inf")

            for heater in heaters:
                closest = min(closest, abs(house - heater))

            answer = max(answer, closest)

        return answer
```

This is correct, but slow.

## Problem With Brute Force

If there are `m` houses and `n` heaters, this checks every pair.

The time complexity is:

```python
O(m * n)
```

The constraints allow up to `3 * 10^4` houses and heaters, so this can become too large.

We need to find the closest heater for each house more efficiently.

## Key Insight

Sort the heaters.

For each house, the closest heater must be either:

1. The nearest heater on the left.
2. The nearest heater on the right.

We can find this position using binary search.

For a house `x`, find the insertion index in sorted `heaters`.

```python
i = bisect_left(heaters, x)
```

Then:

| Candidate | Index |
|---|---|
| Heater on the right | `i` |
| Heater on the left | `i - 1` |

The distance for this house is the smaller of those two distances.

The final radius must cover the worst house, so we take the maximum over all houses.

## Algorithm

Sort `heaters`.

Initialize:

```python
answer = 0
```

For each `house`:

1. Use binary search to find the first heater position greater than or equal to `house`.
2. Compute distance to that heater if it exists.
3. Compute distance to the previous heater if it exists.
4. The house needs the smaller of these distances.
5. Update the answer with the maximum needed distance.

Return `answer`.

## Walkthrough

Use:

```python
houses = [1, 5]
heaters = [2]
```

Sorted heaters:

```python
[2]
```

For house `1`:

```python
insertion index = 0
right heater = 2
distance = 1
```

Needed radius for this house:

```python
1
```

For house `5`:

```python
insertion index = 1
left heater = 2
distance = 3
```

Needed radius for this house:

```python
3
```

The common radius must satisfy every house, so:

```python
max(1, 3) = 3
```

Answer:

```python
3
```

## Correctness

For a fixed house, any heater farther left than the nearest left heater has greater or equal distance to the house.

Any heater farther right than the nearest right heater also has greater or equal distance to the house.

Therefore, the closest heater to a house must be one of the two heaters adjacent to its insertion position in the sorted heater array.

The algorithm computes the minimum distance from each house to one of these closest candidate heaters.

A radius smaller than the maximum of these distances would fail to cover the house that needs that maximum distance.

A radius equal to that maximum covers every house, because every house has some heater within that distance.

Therefore, the returned radius is the minimum possible common radius.

## Complexity

Let:

```python
m = len(houses)
n = len(heaters)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n + m log n)` | Sort heaters, then binary search for each house |
| Space | `O(1)` extra | Only a few variables are used, excluding sorting internals |

## Implementation

```python
from bisect import bisect_left

class Solution:
    def findRadius(self, houses: list[int], heaters: list[int]) -> int:
        heaters.sort()
        answer = 0

        for house in houses:
            i = bisect_left(heaters, house)

            closest = float("inf")

            if i < len(heaters):
                closest = min(closest, heaters[i] - house)

            if i > 0:
                closest = min(closest, house - heaters[i - 1])

            answer = max(answer, closest)

        return answer
```

## Code Explanation

We sort heater positions:

```python
heaters.sort()
```

This allows binary search.

For each house:

```python
i = bisect_left(heaters, house)
```

`i` is the first heater index whose position is at least `house`.

If `i` is valid, there is a heater on the right:

```python
if i < len(heaters):
    closest = min(closest, heaters[i] - house)
```

If `i > 0`, there is a heater on the left:

```python
if i > 0:
    closest = min(closest, house - heaters[i - 1])
```

The house only needs the nearest heater.

The final answer is the largest nearest-heater distance among all houses:

```python
answer = max(answer, closest)
```

## Alternative Two-Pointer Implementation

We can also sort both arrays and move a heater pointer forward when the next heater is closer.

```python
class Solution:
    def findRadius(self, houses: list[int], heaters: list[int]) -> int:
        houses.sort()
        heaters.sort()

        answer = 0
        i = 0

        for house in houses:
            while (
                i + 1 < len(heaters)
                and abs(heaters[i + 1] - house) <= abs(heaters[i] - house)
            ):
                i += 1

            answer = max(answer, abs(heaters[i] - house))

        return answer
```

This runs in:

```python
O(m log m + n log n)
```

because both arrays are sorted, then scanned linearly.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findRadius([1, 2, 3], [2]) == 1
    assert s.findRadius([1, 2, 3, 4], [1, 4]) == 1
    assert s.findRadius([1, 5], [2]) == 3
    assert s.findRadius([1, 2, 3, 4, 5], [10]) == 9
    assert s.findRadius([10], [1, 20]) == 9
    assert s.findRadius([1, 5, 10], [2, 8]) == 3
    assert s.findRadius([282475249, 622650073, 984943658], [823564440]) == 461089191

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3]`, `[2]` | Standard single-heater case |
| `[1,2,3,4]`, `[1,4]` | Houses covered from both ends |
| `[1,5]`, `[2]` | One far house determines radius |
| All houses left of heater | Checks right-only candidate |
| One house between heaters | Checks nearest of two heaters |
| Multiple houses and heaters | General case |
| Large coordinates | Confirms integer distance handling |