Abstract / Summary

Given houses and heaters positions on a line find the minimum radius so every house is within that distance of a heater

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Sorting
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the classic “minimum heating radius” problem. Given positions of houses and heaters on a line, it computes the smallest radius R such that every house lies within distance R of at least one heater. The algorithm first orders the inputs, then walks through the houses while maintaining a pointer into the sorted heater list. For each house it determines the distance to the nearest heater on the left and on the right, keeps the larger of those distances, and finally returns the maximum of all such minima - the required radius.

Key Steps

Normalizing the heater list

The heater positions are sorted and padded with sentinel values representing negative and positive infinity. This guarantees that every house will have a left and a right neighbor in the heater list, eliminating the need for explicit boundary checks during the main loop.

heaters = [float("-inf")] + sorted(heaters) + [float("+inf")]

Initializing the traversal pointer

A pointer pos is set to the first real heater (index 1) because index 0 holds the negative-infinity sentinel. This pointer will advance only forward as houses are processed in ascending order.

pos = 1

Processing houses in sorted order

The houses are sorted to align with the monotonic movement of the heater pointer. For each house h, the inner while loop advances pos until the current heater at heaters[pos] is the first heater whose position is not less than h. This positions the pointer such that heaters[pos-1] is the closest heater on the left and heaters[pos] is the closest heater on the right.

for h in sorted(houses):
    while h > heaters[pos]:
        pos += 1

Computing the nearest distance for a house

Once the correct interval is identified, the distance to the nearest heater is the smaller of the two absolute differences: the gap to the right heater and the gap to the left heater. The min function captures this value in closest.

closest = min(heaters[pos] - h, h - heaters[pos - 1])

Updating the required radius

The algorithm maintains result as the maximum of all closest values seen so far. This reflects the worst-case house that dictates the overall heating radius.

result = max(result, closest)

Returning the final answer

After all houses have been examined, result holds the minimal radius that covers every house, and it is returned.

return result

Edge Cases Handled

The use of sentinel values (-inf and +inf) ensures that houses located to the far left of the first heater or far right of the last heater are still processed correctly. In those situations the distance to the non-existent side becomes infinite, and the min operation automatically selects the finite distance to the existing heater, yielding the correct nearest distance.

When the list of houses is empty, the loop body never executes and result remains at its initial value of 0, which is the appropriate radius for an empty set of houses.

If multiple houses share the same coordinate, sorting does not affect correctness; each duplicate is examined independently, and the same nearest distance is computed each time.

When heaters contain duplicate positions, sorting preserves them, but the sentinel padding still guarantees that the pointer will stop at the first heater not less than the house coordinate, so duplicate heaters do not disturb the interval identification.

Performance Optimizations

The algorithm achieves linear traversal of the combined data after the initial sorting step. By advancing the heater pointer only forward, each heater is examined at most once, avoiding repeated binary searches for every house.

Sentinel values eliminate conditional branches that would otherwise be required to check whether the pointer has reached the ends of the heater list. This reduces the number of comparisons inside the inner loop and streamlines the distance calculation.

Using built-in min and max functions leverages highly optimized native code for the elementary comparisons, contributing to faster execution compared to manual conditional logic.

Overall, the design balances simplicity with efficiency, ensuring that the dominant cost is the unavoidable sorting of the input arrays while keeping the subsequent processing tightly bounded.

Imagine houses lined up along a long, straight street. Some of the houses have heaters inside them, but others are cold. The goal is to make sure every house feels nice and warm. To do this, every heater needs to reach out and cover a certain distance so that even the house furthest from a heater stays cozy.

The first step is to sort the heaters in order from the start of the street to the end. To make things easier to think about, imagine adding an invisible, magical heater way off in the empty space before the first house and another one way off after the last house. These help because every real house will always have a heater somewhere to its left and another one somewhere to its right.

The code looks at each house one by one, moving from the beginning of the street to the end. For every house, it finds which heater is to the left and which heater is to the right. By comparing those two heaters, it calculates the shortest distance to find the nearest warmth.

As it checks each house, it keeps track of the biggest distance it has found so far. This biggest distance represents the amount of coverage needed. By the time every house has been checked, the final number tells exactly how far the heaters need to stretch to keep everyone warm.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java				Python				TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java				Python		Go		TS
	LeetcodeHelp	C++	Java				Python
	Progiez	C++	Java				Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	halfrost								Go
	JoshCrozier			JS
	linouk23	C++
	lkwq007						Python
	lzl124631x	C++
	MacJim	C++
	qiyuangong		Java
	ruoru					Rust
	suxrobGM				C#
	varunu28		Java
	vli02									C
	wisdompeak	C++
	yuanliu666							Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
qiyuangong	Java
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality