LeetCode 475 - Heaters

LeetCode Problem 475

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem gives two arrays, houses and heaters, where each value represents a position on a one dimensional horizontal line. Every heater has the same warming radius, and a house is considered covered if there exists at least one heater whose distance to the house is less than or equal to that radius.

The task is to compute the minimum radius required so that every house is covered by at least one heater.

In other words, for each house we want to know how far away its nearest heater is. Since all heaters must use the same radius, the final answer is the maximum of these minimum distances.

For example, if a house is located at position 5 and the nearest heater is at position 2, then that house requires at least radius 3. If another house only needs radius 1, the overall system must still use radius 3, because every house must be covered.

The constraints are important:

• Up to 3 * 10^4 houses and heaters
• Positions can be as large as 10^9

These limits tell us that a quadratic solution is too slow. A solution that checks every heater for every house would require up to:

$$3 \times 10^4 \times 3 \times 10^4 = 9 \times 10^8$$

operations in the worst case, which is far too large.

The problem also guarantees:

• There is at least one house
• There is at least one heater
• Positions are positive integers

Important edge cases include:

• A single heater covering houses on both sides
• Houses located before the first heater
• Houses located after the last heater
• Multiple heaters at different distances
• Duplicate or closely packed positions
• Very large coordinate values

These cases are important because nearest heater calculations near array boundaries are easy places for off by one errors.

Approaches

Brute Force Approach

The most direct solution is to examine every house and compute its distance to every heater.

For each house:

1. Iterate through all heaters
2. Compute the absolute distance
3. Keep the minimum distance for that house
4. Track the maximum minimum distance across all houses

This works because the nearest heater determines the minimum radius needed for a particular house, and the largest such value determines the global radius.

However, this approach is inefficient. If there are n houses and m heaters, the time complexity becomes O(n * m). With both arrays potentially containing 30,000 elements, this becomes too slow.

Optimal Approach, Sorting + Binary Search

The key observation is that we only care about the nearest heater for each house.

If the heaters are sorted, then for any house we can efficiently locate the closest heater using binary search instead of scanning the entire heater array.

For a given house position:

• Binary search finds the insertion position in the sorted heater array

• The nearest heater must be either:

• The heater immediately to the left

• The heater immediately to the right

There is no need to examine any other heaters because the array is sorted.

This reduces the heater lookup for each house from O(m) to O(log m).

Since we process all houses once, the overall complexity becomes:

$$O(n \log m)$$

plus sorting costs.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Check every heater for every house
Optimal	O(n log n + m log m + n log m)	O(1) or O(log m)	Sort heaters and use binary search

Algorithm Walkthrough

Optimal Algorithm

1. Sort the heaters array.

Sorting allows us to perform binary search efficiently. Once sorted, nearby heaters in terms of position are also nearby in the array. 2. Initialize a variable max_radius = 0.

This variable stores the minimum heater radius required to cover all houses seen so far. 3. Iterate through every house in houses.

For each house, we want to determine the distance to its closest heater. 4. Use binary search to find the insertion position of the current house in the sorted heater array.

This gives the index where the house would be inserted while maintaining sorted order. 5. Compute the distance to the nearest heater on the left.

If the insertion index is greater than 0, then the heater at index - 1 is the closest heater on the left. 6. Compute the distance to the nearest heater on the right.

If the insertion index is smaller than the heater array length, then the heater at index is the closest heater on the right. 7. Take the smaller of the two distances.

Since we only need one heater to cover the house, the nearest heater determines the required radius for that house. 8. Update max_radius.

The final radius must cover every house, so we take the maximum required radius across all houses. 9. Return max_radius.

After processing all houses, this value represents the minimum universal heater radius.

Why it works

After sorting, binary search guarantees that the insertion position splits heaters into two groups:

• All heaters before the insertion point are to the left of the house
• All heaters after the insertion point are to the right

The closest heater must therefore be one of the adjacent heaters around the insertion point. Any farther heater would have a larger distance because the array is sorted.

By computing the nearest heater distance for every house and taking the maximum, we ensure every house is covered while minimizing the shared heater radius.

Python Solution

from bisect import bisect_left
from typing import List

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

        max_radius = 0

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

            left_distance = float("inf")
            right_distance = float("inf")

            if insert_pos > 0:
                left_distance = house - heaters[insert_pos - 1]

            if insert_pos < len(heaters):
                right_distance = heaters[insert_pos] - house

            nearest_distance = min(left_distance, right_distance)

            max_radius = max(max_radius, nearest_distance)

        return max_radius

The implementation begins by sorting the heater positions. This is necessary because binary search only works correctly on sorted data.

For each house, bisect_left finds the position where the house would be inserted into the heater array while preserving order. This insertion point helps identify the closest heaters on both sides.

Two distances are then computed:

• Distance to the nearest heater on the left
• Distance to the nearest heater on the right

If one side does not exist, the distance remains infinity so it cannot incorrectly affect the minimum calculation.

The smaller of the two distances represents the radius required for the current house. The algorithm keeps track of the maximum such value because the final heater radius must cover every house.

Finally, the function returns the maximum required radius.

Go Solution

package main

import (
	"math"
	"sort"
)

func findRadius(houses []int, heaters []int) int {
	sort.Ints(heaters)

	maxRadius := 0

	for _, house := range houses {
		insertPos := sort.SearchInts(heaters, house)

		leftDistance := math.MaxInt32
		rightDistance := math.MaxInt32

		if insertPos > 0 {
			leftDistance = house - heaters[insertPos-1]
		}

		if insertPos < len(heaters) {
			rightDistance = heaters[insertPos] - house
		}

		nearestDistance := min(leftDistance, rightDistance)

		if nearestDistance > maxRadius {
			maxRadius = nearestDistance
		}
	}

	return maxRadius
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version. The primary difference is the use of sort.SearchInts, which performs binary search on a sorted slice.

Go does not provide a built in infinity value for integers, so math.MaxInt32 is used as a sufficiently large placeholder when one side does not exist.

The solution also includes a helper min function because Go does not provide a generic integer minimum function in the standard library.

Since all computations remain within integer bounds defined by the problem constraints, integer overflow is not an issue.

Worked Examples

Example 1

Input:

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

Sorted heaters:

[2]

House	Insert Position	Left Distance	Right Distance	Nearest Distance	Max Radius
1	0	inf	1	1	1
2	0	inf	0	0	1
3	1	1	inf	1	1

Final answer:

1

Example 2

Input:

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

Sorted heaters:

[1,4]

House	Insert Position	Left Distance	Right Distance	Nearest Distance	Max Radius
1	0	inf	0	0	0
2	1	1	2	1	1
3	1	2	1	1	1
4	1	3	0	0	1

Final answer:

1

Example 3

Input:

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

Sorted heaters:

[2]

House	Insert Position	Left Distance	Right Distance	Nearest Distance	Max Radius
1	0	inf	1	1	1
5	1	3	inf	3	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log m + n log m)	Sorting plus binary search for each house
Space	O(1) or O(log m)	Extra space depends on sorting implementation

Let n be the number of houses and m be the number of heaters.

Sorting the heater array costs O(m log m). If we also sort houses, that would add O(n log n), although this implementation does not require it.

For each house, binary search on the heater array takes O(log m), resulting in O(n log m) total lookup time.

The algorithm uses only a few extra variables beyond the input arrays, so auxiliary space usage is minimal.

Test Cases

from typing import List

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        from bisect import bisect_left

        heaters.sort()

        max_radius = 0

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

            left_distance = float("inf")
            right_distance = float("inf")

            if insert_pos > 0:
                left_distance = house - heaters[insert_pos - 1]

            if insert_pos < len(heaters):
                right_distance = heaters[insert_pos] - house

            max_radius = max(max_radius, min(left_distance, right_distance))

        return max_radius

solution = Solution()

assert solution.findRadius([1, 2, 3], [2]) == 1
# Single heater covering houses on both sides

assert solution.findRadius([1, 2, 3, 4], [1, 4]) == 1
# Two heaters at boundaries

assert solution.findRadius([1, 5], [2]) == 3
# House far away from heater

assert solution.findRadius([1], [1]) == 0
# House exactly on heater

assert solution.findRadius([1, 10], [5]) == 5
# Single heater in middle

assert solution.findRadius([1, 2, 3, 100], [1, 50]) == 50
# Large uncovered gap

assert solution.findRadius([1, 5, 9], [2, 8]) == 3
# Multiple heaters with varying distances

assert solution.findRadius([1, 2, 3], [1, 2, 3]) == 0
# Every house has exact heater

assert solution.findRadius([1000000000], [1]) == 999999999
# Very large coordinate values

assert solution.findRadius([1, 2, 3, 4, 5], [3]) == 2
# Heater centered among houses

Test Summary

Test	Why
[1,2,3], [2]	Basic single heater scenario
[1,2,3,4], [1,4]	Coverage from both ends
[1,5], [2]	Large distance requirement
[1], [1]	Exact overlap case
[1,10], [5]	Heater between distant houses
[1,2,3,100], [1,50]	Large uncovered range
[1,5,9], [2,8]	Nearest heater selection
[1,2,3], [1,2,3]	Zero radius needed
[1000000000], [1]	Large coordinate handling
[1,2,3,4,5], [3]	Symmetric distances

Edge Cases

One important edge case occurs when all houses lie to the left of the first heater or to the right of the last heater. In these situations, binary search returns either 0 or len(heaters). A buggy implementation might attempt to access an invalid index. This solution safely checks array bounds before computing distances.

Another important case is when a house is positioned exactly on a heater. The correct required distance is 0, but implementations using strict inequalities can accidentally return a positive value. Using bisect_left correctly identifies the heater position and computes a zero distance.

Large coordinate values are another potential source of issues. Since positions may reach 10^9, implementations that use smaller integer types could overflow during subtraction. Both Python and Go handle these values safely with their integer representations.

A subtle edge case involves multiple heaters surrounding a house at different distances. The algorithm must correctly compare both the left and right candidate heaters and choose the smaller distance. Because the heater array is sorted, checking only the immediate neighbors around the insertion point is sufficient and guarantees correctness.