Watch 10 video solutions for Heaters, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Pepcoding has 9,918 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.
Every house can be warmed, as long as the house is within the heater's warm radius range.
Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.
Notice that all the heaters follow your radius standard, and the warm radius will the same.
Example 1:
Input: houses = [1,2,3], heaters = [2] Output: 1 Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: houses = [1,2,3,4], heaters = [1,4] Output: 1 Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.
Example 3:
Input: houses = [1,5], heaters = [2] Output: 3
Constraints:
1 <= houses.length, heaters.length <= 3 * 1041 <= houses[i], heaters[i] <= 109Problem Overview: You get positions of houses and heaters on a number line. Each heater warms houses within a fixed radius. The task is to compute the minimum radius required so every house is covered by at least one heater.
The challenge is efficiently finding the nearest heater for every house. A naive approach checks every heater for every house, but that becomes slow when both arrays are large. Efficient solutions rely on sorting and searching techniques.
Approach 1: Binary Search on Heaters (Time: O(n log m), Space: O(1) or O(log m))
Sort the heaters array first. For each house, use binary search to locate the closest heater position. Specifically, find the insertion point of the house in the sorted heaters list and compare the distance to the heater on the left and right. The minimum of those two distances is the radius required for that house. Track the maximum radius across all houses because every house must be covered. This method works well because each lookup becomes a log m operation instead of scanning all heaters. The approach relies heavily on binary search and sorted arrays.
Approach 2: Two Pointers Method (Time: O(n log n + m log m) due to sorting, Space: O(1))
Sort both houses and heaters. Then walk through houses with one pointer while maintaining another pointer for heaters. Move the heater pointer whenever the next heater is closer to the current house than the current one. This effectively keeps the nearest heater candidate as you iterate. For each house, compute the absolute distance to the chosen heater and update the maximum radius needed. Because each pointer only moves forward, the scanning phase is linear. This approach combines two pointers with sorting to avoid repeated binary searches.
The key insight for both solutions is identical: every house only cares about its nearest heater. The global radius must be large enough to cover the worst-case house. Instead of trying every possible radius, compute the minimal distance for each house and take the maximum.
Recommended for interviews: The binary search approach is the most common expectation because it directly models “find closest element in a sorted array.” It clearly demonstrates understanding of lower_bound-style searches. The two pointers approach is slightly faster in practice after sorting and shows strong algorithmic intuition. Mentioning both approaches signals solid mastery of array searching patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Heaters | O(n log m) | O(1) | When heaters are sorted and you want direct nearest-heater lookup per house |
| Two Pointers Method | O(n log n + m log m) | O(1) | When both arrays can be sorted and you want a linear scan after sorting |