Heaters: Binary Search for Minimum Radius

Heaters is LeetCode 475, and it is a clean application of binary search to a geometry-flavored problem. You are given houses and heaters on a number line, and you need to find the smallest radius such that every house is within range of at least one heater. The trick is recognizing that for each house, you only need to find the nearest heater -- and that is exactly what binary search does efficiently on a sorted array.

The problem

You are given two arrays: houses and heaters, both representing positions on a number line. You need to find the minimum radius such that every house is covered by at least one heater. A heater at position p with radius r covers all positions from p - r to p + r.

Example: houses = [1, 2, 3, 4], heaters = [1, 4].

The answer is 1. Heater at position 1 covers houses at 1 and 2 (within distance 1). Heater at position 4 covers houses at 3 and 4 (within distance 1). Every house is covered, and no smaller radius works.

The approach

The key insight is that the required radius is determined by the house that is farthest from its nearest heater. If you can find the nearest heater for every house, the answer is just the maximum of all those minimum distances.

Here is the plan:

1. Sort the heaters array. This lets you binary search for the nearest heater in O(log m) time per house.
2. For each house, binary search the sorted heaters to find the closest one. Check both the heater just before and just after the house's position, and take the smaller distance.
3. Track the maximum of all these minimum distances. That maximum is the answer -- the minimum radius that covers every house.

This works because the radius must be large enough for the worst-case house. If you set the radius to cover the farthest house, every closer house is automatically covered too.

The code

import bisect

def findRadius(houses, heaters):
    heaters.sort()
    result = 0

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

        left_dist = float('inf')
        right_dist = float('inf')

        if i > 0:
            left_dist = house - heaters[i - 1]
        if i < len(heaters):
            right_dist = heaters[i] - house

        nearest = min(left_dist, right_dist)
        result = max(result, nearest)

    return result

Let's walk through each piece:

• heaters.sort() sorts the heaters so binary search works. This is O(m log m).
• bisect.bisect_left(heaters, house) finds the insertion point for house in the sorted heaters array. This is the index of the first heater that is greater than or equal to house.
• left_dist is the distance to the heater just before the insertion point (the largest heater that is still to the left of the house). If there is no such heater, the distance is infinity.
• right_dist is the distance to the heater at the insertion point (the smallest heater that is at or to the right of the house). If the insertion point is past the end, the distance is infinity.
• nearest = min(left_dist, right_dist) picks whichever heater is closer.
• result = max(result, nearest) keeps track of the worst-case house, because the radius must handle this house.

Visual walkthrough

Let's trace through houses = [1, 2, 3, 4] and heaters = [1, 4]. After sorting heaters (already sorted), we binary search for each house.

Four houses checked, each with a binary search. The maximum minimum distance is 1, so the answer is 1. With radius 1, every house reaches at least one heater.

Complexity analysis

This is efficient. Even with 30,000 houses and 30,000 heaters (the LeetCode constraints), the total work is roughly 30,000 * 15 = 450,000 operations. Very fast.

The building blocks

This problem is built from two core building blocks:

Binary search for nearest neighbor. Given a sorted array and a target value, find the closest element. You use bisect_left to find the insertion point, then compare the elements on either side. This same technique shows up whenever you need to find the closest value in a sorted collection -- scheduling problems, coordinate geometry, interval queries, and more.

Max of minimums. The answer is not the minimum distance for any single house. It is the maximum across all houses of their individual minimum distances. This "minimax" framing is common in optimization problems: you are minimizing the worst case. Recognizing this pattern helps you avoid overcomplicating the solution.

Together, these two ideas make the solution almost mechanical: sort, binary search per element, track the max.

Edge cases

• House exactly on a heater. Distance is 0. The binary search handles this naturally because bisect_left returns the index of the matching heater, and right_dist will be 0.
• Single heater. Every house must be covered by the same heater. The answer is the maximum distance from any house to that one heater.
• Single house. The answer is the distance from that house to the nearest heater. Only one binary search needed.
• All houses and heaters at the same position. Radius is 0. Every distance is 0, so the max is 0.
• Houses outside the range of all heaters. The edge houses might only have a heater on one side. The binary search handles this because one of left_dist or right_dist will be infinity, and the other will be the actual distance.

From understanding to recall

The logic here is clean: sort the heaters, binary search for each house, take the max of the minimum distances. You probably get it right now.

But writing it under pressure is a different story. Which bisect function do you use -- bisect_left or bisect_right? Do you check i and i - 1, or i and i + 1? What happens when i is 0 or len(heaters)? These details are small, but getting them wrong means a wrong answer or an index-out-of-bounds error.

Spaced repetition locks in the details. You write the solution from scratch today, then again tomorrow, then in three days. After a few rounds, the bisect_left plus check-both-neighbors pattern becomes automatic. You stop worrying about off-by-one boundary checks because you have written them correctly enough times that they are muscle memory.

Related posts

• Binary Search (LeetCode 704): The Foundation - The core binary search template that this problem's per-house search is built on
• Search Insert Position - Another problem where the insertion point from binary search is the key to the answer
• Find First and Last Position of Element in Sorted Array - Practice with bisect_left and bisect_right to find boundaries in sorted arrays