Heaters — Solution in Python, Java & C++
Heaters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Heaters is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Houses and heaters stand at integer positions on a straight road: houses[i] is the position of a house and heaters[j] the position of a heater. Neither array is sorted, and a position may appear more than once.
Every heater is set to the same warming radius r: a heater at p warms every house whose position lies in [p - r, p + r].
Return the smallest non-negative integer radius that warms every house.
Example 1
Input: houses = [1,5], heaters = [2]
Output: 3
Explanation: The single heater must reach the house at 5, three steps away.
Example 2
Input: houses = [3,9,14], heaters = [12,4]
Output: 3
Explanation: House 3 is 1 from heater 4, house 9 is 3 from heater 12 and house 14 is 2 from heater 12; the worst house needs 3.
Example 3
Input: houses = [7], heaters = [7]
Output: 0
Constraints
1 <= houses.length, heaters.length <= 3 * 10^41 <= houses[i], heaters[j] <= 10^9
Hints for Heaters
Hint 1
The radius has to cover the house that is farthest from its nearest heater, so the answer is a maximum over houses of a minimum over heaters.
Hint 2
For one house only two heaters matter: the closest one at or to its right and the closest one to its left.
Hint 3
Sort the heaters and binary-search each house's insertion point; take the smaller of the two neighbouring distances.
How to solve Heaters
The minimum radius equals the largest distance from any house to its nearest heater. With the heaters sorted, a house's nearest heater is one of the two that bracket its position, which binary search finds in logarithmic time.
Approach
- Sort a copy of
heaters. - For each house at
x, find the first heater indexiwithheaters[i] >= x(lower bound). - The house's distance is the smaller of
heaters[i] - x(ifiis in range) andx - heaters[i - 1](ifi > 0). - Return the maximum of these distances over all houses.
Why it works
A radius r warms a house exactly when some heater lies within r of it, i.e. when r is at least the house's nearest-heater distance. So r works for all houses precisely when it is at least the largest of those distances, and that largest distance is the minimum. Among heaters on the right of x the first is the closest, and among those on the left the last is the closest, so the two bracketing heaters are the only candidates.
Complexity
- Time —
O((n + m) log m) - Space —
O(m) for the sorted copy
Pitfalls
- A house to the left of every heater (or right of every heater) has only one neighbour — guard both indices.
- Houses do not need sorting for the binary-search version; only the heaters do.
- The answer is a maximum of minima — taking the minimum over all pairs answers a different question.
Reference solution
Python
from typing import List
import bisect
def findRadius(houses: List[int], heaters: List[int]) -> int:
hs = sorted(heaters)
best = 0
for x in houses:
i = bisect.bisect_left(hs, x)
d = 1 << 31
if i < len(hs):
d = hs[i] - x
if i > 0:
d = min(d, x - hs[i - 1])
best = max(best, d)
return bestJava
public static int findRadius(int[] houses, int[] heaters) {
int[] hs = heaters.clone();
Arrays.sort(hs);
int best = 0;
for (int x : houses) {
int lo = 0, hi = hs.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (hs[mid] < x) lo = mid + 1; else hi = mid;
}
int d = Integer.MAX_VALUE;
if (lo < hs.length) d = hs[lo] - x;
if (lo > 0) d = Math.min(d, x - hs[lo - 1]);
best = Math.max(best, d);
}
return best;
}C++
int findRadius(vector<int>& houses, vector<int>& heaters) {
vector<int> hs(heaters);
sort(hs.begin(), hs.end());
int best = 0;
for (int x : houses) {
int i = lower_bound(hs.begin(), hs.end(), x) - hs.begin();
int d = INT_MAX;
if (i < (int)hs.size()) d = hs[i] - x;
if (i > 0) d = min(d, x - hs[i - 1]);
best = max(best, d);
}
return best;
}JavaScript
var findRadius = function(houses, heaters) {
var hs = heaters.slice().sort(function(a, b) { return a - b; });
var best = 0;
for (var i = 0; i < houses.length; i++) {
var x = houses[i];
var lo = 0, hi = hs.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (hs[mid] < x) lo = mid + 1; else hi = mid;
}
var d = 2147483647;
if (lo < hs.length) d = hs[lo] - x;
if (lo > 0 && x - hs[lo - 1] < d) d = x - hs[lo - 1];
if (d > best) best = d;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms