Heaters
Heaters is a medium binary search problem solved with the bisect pattern.
The best approach, optimal (sort heaters + binary search), runs in O((n + m) log m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every heater for every house) up.
Problem
Houses and heaters stand on a straight line. You are given their positions in two integer arrays, houses and heaters. All heaters share the same warming radius r: a heater at position t warms every house at a position within distance r of t.
Return the smallest radius r such that every house is warmed by at least one heater.
Examples
Example 1
- Input
houses = [2, 5, 9, 14], heaters = [4, 12]- Output
3- Why
- House 9 is 3 away from heater 12 (and 5 away from heater 4); every other house is at most 2 from its nearest heater.
Example 2
- Input
houses = [1, 6], heaters = [6]- Output
5- Why
- House 1 is 5 away from the only heater.
Example 3
- Input
houses = [7, 3, 10], heaters = [10, 3, 7]- Output
0- Why
- Every house has a heater at its own position, so radius 0 is enough.
Constraints
1 <= houses.length, heaters.length <= 3 · 10^41 <= houses[i], heaters[i] <= 10^9- Neither array is necessarily sorted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check every heater for every house) | O(n · m) | O(1) |
| Optimal (sort heaters + binary search) | O((n + m) log m) | O(1) |
1Brute force (check every heater for every house)
O(n · m)Every house is compared with every heater.O(1)Two running values.For each house, compute the distance to every heater and keep the smallest. The answer is the largest of these per-house minimums.
- answer = 0.
- For each house h: nearest = min over heaters t of |h - t|.
- answer = max(answer, nearest).
class Solution {
public int findRadius(int[] houses, int[] heaters) {
int answer = 0;
for (int h : houses) {
int nearest = Integer.MAX_VALUE;
for (int t : heaters) nearest = Math.min(nearest, Math.abs(h - t));
answer = Math.max(answer, nearest);
}
return answer;
}
}class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
answer = 0
for h in houses:
nearest = min(abs(h - t) for t in heaters)
answer = max(answer, nearest)
return answerclass Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int answer = 0;
for (int h : houses) {
int nearest = INT_MAX;
for (int t : heaters) nearest = min(nearest, abs(h - t));
answer = max(answer, nearest);
}
return answer;
}
};function findRadius(houses, heaters) {
let answer = 0;
for (const h of houses) {
let nearest = Infinity;
for (const t of heaters) nearest = Math.min(nearest, Math.abs(h - t));
answer = Math.max(answer, nearest);
}
return answer;
}2Optimal (sort heaters + binary search)
O((n + m) log m)Sorting the heaters costs O(m log m), then each house does one O(log m) search.O(1)Sorting in place; apart from that only a few variables (the sort itself may use O(log m) stack).Sort the heaters. For each house, binary-search the first heater at or to the right of it. The nearest heater is either that one or the one just before it, so only two distances need checking. Take the maximum over all houses.
- Sort heaters.
- For each house h, find idx = first index with heaters[idx] >= h (lower bound).
- right = heaters[idx] - h if idx < m; left = h - heaters[idx - 1] if idx > 0.
- nearest = min(left, right); answer = max(answer, nearest).
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int m = heaters.length, answer = 0;
for (int h : houses) {
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (heaters[mid] < h) lo = mid + 1;
else hi = mid;
}
int nearest = Integer.MAX_VALUE;
if (lo < m) nearest = heaters[lo] - h;
if (lo > 0) nearest = Math.min(nearest, h - heaters[lo - 1]);
answer = Math.max(answer, nearest);
}
return answer;
}
}class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
heaters.sort()
m = len(heaters)
answer = 0
for h in houses:
idx = bisect.bisect_left(heaters, h)
nearest = inf
if idx < m:
nearest = heaters[idx] - h
if idx > 0:
nearest = min(nearest, h - heaters[idx - 1])
answer = max(answer, nearest)
return answerclass Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int m = heaters.size(), answer = 0;
for (int h : houses) {
int idx = lower_bound(heaters.begin(), heaters.end(), h) - heaters.begin();
int nearest = INT_MAX;
if (idx < m) nearest = heaters[idx] - h;
if (idx > 0) nearest = min(nearest, h - heaters[idx - 1]);
answer = max(answer, nearest);
}
return answer;
}
};function findRadius(houses, heaters) {
heaters.sort((a, b) => a - b);
const m = heaters.length;
let answer = 0;
for (const h of houses) {
let lo = 0, hi = m;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (heaters[mid] < h) lo = mid + 1;
else hi = mid;
}
let nearest = Infinity;
if (lo < m) nearest = heaters[lo] - h;
if (lo > 0) nearest = Math.min(nearest, h - heaters[lo - 1]);
answer = Math.max(answer, nearest);
}
return answer;
}Edge cases to test
- A single heater far from all houses
- Houses to the left of every heater or to the right of every heater
- Heaters at exactly the same positions as houses (answer 0)
- Unsorted input and repeated positions
Hints
Hint 1
The radius must reach every house, so the answer is the largest 'distance from a house to its nearest heater'.
Hint 2
If the heaters are sorted, the nearest heater to a house is either the first heater at or after it, or the one just before that.
Hint 3
Binary search finds that position in O(log m) per house.
FAQ
What is the best time complexity for Heaters?
Optimal (sort heaters + binary search) runs in O((n + m) log m) time and O(1) extra space. Sorting the heaters costs O(m log m), then each house does one O(log m) search.
Which pattern does Heaters use?
It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.
Is there a brute force solution for Heaters?
Yes. Brute force (check every heater for every house) takes O(n · m) time and O(1) space. For each house, compute the distance to every heater and keep the smallest.
Which edge cases should I test for Heaters?
A single heater far from all houses; Houses to the left of every heater or to the right of every heater; Heaters at exactly the same positions as houses (answer 0); Unsorted input and repeated positions.