Heaters - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Binary Search on Heaters
Using binary search is an efficient way to find the minimum radius required so that every house is within range of at least one heater. First, sort the heaters array to facilitate the binary search. For each house, determine the closest left and right heaters and calculate the distances. The maximum distance for any house will determine the required radius.
The C solution sorts the heaters and uses a binary search to find the closest heater position for each house. It calculates the distance from each house to the nearest left and right heaters and updates the radius if a larger distance is found.
Complexity
Time Complexity: O(n log n) due to the sorting of the heaters and O(m log n) for binary searches, where m is the number of houses and n is the number of heaters.
Space Complexity: O(1) as we are not using any extra space proportional to the input size.
Approach 2: Two Pointers Method
The two-pointer technique can be used as an alternative. By sorting both the houses and heaters, we can efficiently determine the minimal radius by iterating over the two lists with two pointers. For each house, move the heater pointer to find the closest heater, updating the minimum radius as we go.
In this C solution, the houses and heaters arrays are sorted. For each house, the code searches for the closest heater using a two-pointer approach, dynamically updating the radius as necessary.
Complexity
Time Complexity: O(n log n + m log m), sorting both arrays, and O(n + m) iterating through all houses and heaters.
Space Complexity: O(1), no additional space is used.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search on Heaters | Time Complexity: O(n log n) due to the sorting of the heaters and O(m log n) for binary searches, where m is the number of houses and n is the number of heaters. Space Complexity: O(1) as we are not using any extra space proportional to the input size. |
| Two Pointers Method | Time Complexity: O(n log n + m log m), sorting both arrays, and O(n + m) iterating through all houses and heaters. Space Complexity: O(1), no additional space is used. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Heaters | Leetcode 475 Solution | Searching and Sorting • Pepcoding • 10,214 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Heaters easy or hard?
How to solve Heaters in O(n)?
What is the best approach for Heaters?
What data structure is used in Heaters?
What is the time complexity of Heaters?
Heaters Python or Java solution approach?
Is Heaters asked at Google, Amazon, or Meta interviews?
Ready to solve this problem?
Practice Heaters with our built-in code editor and test cases.
Practice on FleetCode