LeetCode 475: Heaters

Problem Restatement

We are given two arrays:

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:

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

Function shape:

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

Examples

Example 1:

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

The heater at 2 covers:

1 with distance 1
2 with distance 0
3 with distance 1

So the minimum radius is:

1

Example 2:

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:

1

Example 3:

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:

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.

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:

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.

i = bisect_left(heaters, x)

Then:

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:

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:

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

Sorted heaters:

[2]

For house 1:

insertion index = 0
right heater = 2
distance = 1

Needed radius for this house:

1

For house 5:

insertion index = 1
left heater = 2
distance = 3

Needed radius for this house:

3

The common radius must satisfy every house, so:

max(1, 3) = 3

Answer:

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:

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

Implementation

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:

heaters.sort()

This allows binary search.

For each house:

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:

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

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

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:

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.

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:

O(m log m + n log n)

because both arrays are sorted, then scanned linearly.

Testing

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: