Heaters solution and explanation
IBM
Google
9 more videos on this problem
Heaters | Leetcode 475 Solution | Searching and SortingPepcoding · 27:18 · 10K views
Heaters problem (LeetCode #475) - Inside codeInside code · 14:19 · 9K views
Leetcode 475. Heaters [Java] P.S. Explanation with nice picturesif else statement · 11:26 · 3K views
LeetCode 475. Heaters Explanation and Solutionhappygirlzt · 8:30 · 3K views
Heaters | LeetCode - 475 | Binary search | Interview QuestionsAdi Talks Code · 14:01 · 1K views
LeetCode in Python 475. Heaters - Michelle小梦想家Michelle小梦想家 · 25:29 · 1K views
HeatersScott · 8:10 · 855 views
LeetCode 475: Heaters ✅✅ JAVA Solution 👌👌 TC: O(N); SC:O(1)Think Up · 14:31 · 725 views
Leetcode 475. HeatersSunny Gupta · 18:21 · 720 views
AMAZON INTERVIEW QUESTION | Heaters (LeetCode problem 475)MCCOMP · 9:56 · 693 views
The problem
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.
def findRadius(houses, heaters):
heaters.sort()
radius = 0
for house in houses:
pos = bisect.bisect_left(heaters, house)
leftDist = float('inf') if pos == 0 else house - heaters[pos - 1]
rightDist = float('inf') if pos == len(heaters) else heaters[pos] - house
currRadius = min(leftDist, rightDist)
radius = max(radius, currRadius)
return radius
houses = [1, 5]
heaters = [2]
print(findRadius(houses, heaters))import java.util.Arrays;
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int radius = 0;
for (int house : houses) {
int pos = Arrays.binarySearch(heaters, house);
if (pos < 0) {
pos = -pos - 1;
}
int leftDist = (pos == 0) ? Integer.MAX_VALUE : house - heaters[pos - 1];
int rightDist = (pos == heaters.length) ? Integer.MAX_VALUE : heaters[pos] - house;
int currRadius = Math.min(leftDist, rightDist);
radius = Math.max(radius, currRadius);
}
return radius;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] houses = {1, 2, 3, 4};
int[] heaters = {1, 4};
System.out.println(sol.findRadius(houses, heaters));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int radius = 0;
for (auto house : houses) {
auto it = lower_bound(heaters.begin(), heaters.end(), house);
int leftDist = (it == heaters.begin()) ? INT_MAX : house - *(it - 1);
int rightDist = (it == heaters.end()) ? INT_MAX : *it - house;
int currRadius = min(leftDist, rightDist);
radius = max(radius, currRadius);
}
return radius;
}
int main() {
vector<int> houses = {1, 5};
vector<int> heaters = {2};
cout << findRadius(houses, heaters) << endl;
return 0;
}function findRadius(houses, heaters) {
heaters.sort((a, b) => a - b);
let radius = 0;
for (let house of houses) {
let pos = binarySearch(heaters, house);
let leftDist = pos === 0 ? Infinity : house - heaters[pos - 1];
let rightDist = pos === heaters.length ? Infinity : heaters[pos] - house;
radius = Math.max(radius, Math.min(leftDist, rightDist));
}
return radius;
}
function binarySearch(heaters, target) {
let left = 0, right = heaters.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (heaters[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
let houses = [1, 2, 3, 4];
let heaters = [1, 4];
console.log(findRadius(houses, heaters));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int binarySearch(int* heaters, int heatersSize, int target) {
int left = 0, right = heatersSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (heaters[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int findRadius(int* houses, int housesSize, int* heaters, int heatersSize) {
qsort(heaters, heatersSize, sizeof(int), compare);
int radius = 0;
for (int i = 0; i < housesSize; i++) {
int pos = binarySearch(heaters, heatersSize, houses[i]);
int leftDist = (pos == 0) ? INT_MAX : houses[i] - heaters[pos - 1];
int rightDist = (pos == heatersSize) ? INT_MAX : heaters[pos] - houses[i];
int currRadius = leftDist < rightDist ? leftDist : rightDist;
if (currRadius > radius) {
radius = currRadius;
}
}
return radius;
}
int main() {
int houses[] = {1, 2, 3, 4};
int heaters[] = {1, 4};
int radius = findRadius(houses, 4, heaters, 2);
printf("%d\n", radius);
return 0;
}using System;
public class Solution {
public int FindRadius(int[] houses, int[] heaters) {
Array.Sort(heaters);
int radius = 0;
foreach (var house in houses) {
int pos = Array.BinarySearch(heaters, house);
if (pos < 0) {
pos = ~pos;
}
int leftDist = (pos == 0) ? int.MaxValue : house - heaters[pos - 1];
int rightDist = (pos == heaters.Length) ? int.MaxValue : heaters[pos] - house;
int currRadius = Math.Min(leftDist, rightDist);
radius = Math.Max(radius, currRadius);
}
return radius;
}
public static void Main() {
var solution = new Solution();
int[] houses = {1, 5};
int[] heaters = {2};
Console.WriteLine(solution.FindRadius(houses, heaters));
}
}The Python solution uses the bisect module for efficient searching. It computes the distance to the nearest heaters on either side and updates the radius accordingly.
Time Complexity: O(n log n) for sorting the heaters, followed by O(m log n) for each house's search operation.
Space Complexity: O(1) since no extra storage other than input is used.
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.
def findRadius(houses, heaters):
houses.sort()
heaters.sort()
i = 0
radius = 0
for house in houses:
while i < len(heaters) - 1 and abs(heaters[i + 1] - house) <= abs(heaters[i] - house):
i += 1
radius = max(radius, abs(heaters[i] - house))
return radius
houses = [1, 5]
heaters = [2]
print(findRadius(houses, heaters))import java.util.Arrays;
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int i = 0, radius = 0;
for (int house : houses) {
while (i < heaters.length - 1 && Math.abs(heaters[i + 1] - house) <= Math.abs(heaters[i] - house)) {
i++;
}
radius = Math.max(radius, Math.abs(heaters[i] - house));
}
return radius;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] houses = {1, 2, 3, 4};
int[] heaters = {1, 4};
System.out.println(sol.findRadius(houses, heaters));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int i = 0, j = 0, radius = 0;
while (i < houses.size()) {
while (j < heaters.size() - 1 && abs(heaters[j + 1] - houses[i]) <= abs(heaters[j] - houses[i])) {
j++;
}
radius = max(radius, abs(heaters[j] - houses[i]));
i++;
}
return radius;
}
int main() {
vector<int> houses = {1, 5};
vector<int> heaters = {2};
cout << findRadius(houses, heaters) << endl;
return 0;
}function findRadius(houses, heaters) {
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
let i = 0, radius = 0;
for (let house of houses) {
while (i < heaters.length - 1 && Math.abs(heaters[i + 1] - house) <= Math.abs(heaters[i] - house)) {
i++;
}
radius = Math.max(radius, Math.abs(heaters[i] - house));
}
return radius;
}
let houses = [1, 2, 3, 4];
let heaters = [1, 4];
console.log(findRadius(houses, heaters));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int findRadius(int* houses, int housesSize, int* heaters, int heatersSize) {
qsort(houses, housesSize, sizeof(int), compare);
qsort(heaters, heatersSize, sizeof(int), compare);
int i = 0, j = 0, radius = 0;
while (i < housesSize) {
while (j < heatersSize - 1 && abs(heaters[j + 1] - houses[i]) <= abs(heaters[j] - houses[i])) {
j++;
}
int currRadius = abs(heaters[j] - houses[i]);
if (currRadius > radius) {
radius = currRadius;
}
i++;
}
return radius;
}
int main() {
int houses[] = {1, 2, 3, 4};
int heaters[] = {1, 4};
int radius = findRadius(houses, 4, heaters, 2);
printf("%d\n", radius);
return 0;
}using System;
public class Solution {
public int FindRadius(int[] houses, int[] heaters) {
Array.Sort(houses);
Array.Sort(heaters);
int i = 0, radius = 0;
foreach (int house in houses) {
while (i < heaters.Length - 1 && Math.Abs(heaters[i + 1] - house) <= Math.Abs(heaters[i] - house)) {
i++;
}
radius = Math.Max(radius, Math.Abs(heaters[i] - house));
}
return radius;
}
public static void Main() {
var solution = new Solution();
int[] houses = {1, 5};
int[] heaters = {2};
Console.WriteLine(solution.FindRadius(houses, heaters));
}
}The Python solution sorts the houses and heaters and uses comparison in a loop with an index tracking closest heaters to adjust the radius correctly.
Time Complexity: O(n log n + m log m) for sorting, O(n + m) using two-pointer method for iteration.
Space Complexity: O(1), performed in-place without extra data storage.
Approach 3: Default Approach
function findRadius(houses: number[], heaters: number[]): number {
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
const m = houses.length,
n = heaters.length;
let ans = 0;
for (let i = 0, j = 0; i < m; i++) {
let cur = Math.abs(houses[i] - heaters[j]);
while (
j + 1 < n &&
Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])
) {
cur = Math.min(Math.abs(houses[i] - heaters[++j]), cur);
}
ans = Math.max(cur, ans);
}
return ans;
}func findRadius(houses []int, heaters []int) int {
sort.Ints(houses)
sort.Ints(heaters)
m, n := len(houses), len(heaters)
check := func(r int) bool {
var i, j int
for i < m {
if j >= n {
return false
}
mi, mx := heaters[j]-r, heaters[j]+r
if houses[i] < mi {
return false
}
if houses[i] > mx {
j++
} else {
i++
}
}
return true
}
left, right := 0, int(1e9)
for left < right {
mid := (left + right) >> 1
if check(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Heaters | Time Complexity: O(n log n) for sorting the heaters, followed by O(m log n) for each house's search operation. Space Complexity: O(1) since no extra storage other than input is used. |
| Two Pointers Method | Time Complexity: O(n log n + m log m) for sorting, O(n + m) using two-pointer method for iteration. Space Complexity: O(1), performed in-place without extra data storage. |
| Default Approach | – |
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 |
Frequently asked questions
Is Heaters easy or hard?
Heaters is generally considered a medium-level problem. The main difficulty comes from recognizing that each house only needs its nearest heater and implementing an efficient search using binary search or two pointers.
How to solve Heaters in O(n)?
An almost linear scan is possible after sorting both arrays. Sort houses and heaters, then use two pointers to keep track of the closest heater while iterating through houses. Each pointer only moves forward, so the scanning step runs in O(n + m) after sorting.
What is the best approach for Heaters?
The most common approach uses binary search on the heaters array. After sorting heaters, perform a binary search for each house to find the nearest heater on the left and right. The distance to the closest heater determines the radius needed for that house. The final answer is the maximum of these distances, giving O(n log m) time complexity.
What data structure is used in Heaters?
The problem mainly uses arrays with sorting and searching techniques. Efficient solutions rely on binary search over a sorted heaters array or a two-pointer traversal over sorted houses and heaters.
What is the time complexity of Heaters?
The binary search solution runs in O(n log m), where n is the number of houses and m is the number of heaters. Each house performs a logarithmic search in the heaters array. The two-pointer solution runs in O(n log n + m log m) due to sorting, followed by a linear scan.
Heaters Python or Java solution approach?
Python and Java implementations typically sort the heaters array and use binary search functions such as bisect in Python or Arrays.binarySearch in Java. Another common implementation sorts both arrays and applies a two-pointer scan to track the closest heater for each house.
Is Heaters asked at Google, Amazon, or Meta interviews?
Heaters is a classic array searching problem commonly reported in interviews at large tech companies such as Amazon and Google. It tests binary search reasoning, nearest-element logic, and handling sorted arrays efficiently.