Last updated on February 2nd, 2025 at 04:59 am
Here, we see a Heaters LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Binary-Search
Companies
Level of Question
Medium
Heaters LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is evident because the code leverages binary search to efficiently find the closest heater for each house. The binary search is used to minimize the distance between a house and its nearest heater, which is a key characteristic of the Modified Binary Search pattern.
3. Code Implementation in Different Languages
3.1 Heaters C++
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int radius = 0;
sort(heaters.begin(), heaters.end());
for(auto house : houses) {
if(house <= heaters.front()) {
radius = max(radius, heaters.front() - house);
continue;
}
if(house >= heaters.back()) {
radius = max(radius, house - heaters.back());
continue;
}
radius = max(radius, findAjacentHeaters(house, heaters));
}
return radius;
}
private:
int findAjacentHeaters(int house, vector<int>& heaters) {
int radius = 0;
int l = 0;
int r = heaters.size() - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(heaters[mid] == house) return 0;
if(heaters[mid] < house) l = mid + 1;
if(heaters[mid] > house) r = mid - 1;
}
return min(heaters[l]-house, house-heaters[r]);
}
};
3.2 Heaters Java
class Solution {
public int findRadius(int[] houses, int[] heaters) {
if(houses == null || houses.length == 0 || heaters == null || heaters.length == 0){
return 0;
}
Arrays.sort(houses);
Arrays.sort(heaters);
int n = houses.length;
int m = heaters.length;
int i = 0;
int j = 0;
int res = 0;
while(i < n && j < m){
int dist1 = Math.abs(heaters[j] - houses[i]);
int dist2 = Integer.MAX_VALUE;
if(j + 1 < m){
dist2 = Math.abs(heaters[j + 1] - houses[i]);
}
if(dist1 < dist2){
res = Math.max(res, dist1);
i++;
}else{
j++;
}
}
return res;
}
}
3.3 Heaters JavaScript
var findRadius = function(houses, heaters) {
heaters.sort((a, b) => a - b);
return Math.max(...houses.map(h => findMinDistance(h, heaters)));
};
const findMinDistance = (house, heaters) => {
let left = 0;
let right = heaters.length - 1;
while (left <= right) {
const mid = left + ((right - left) >> 1);
if (heaters[mid] <= house && house <= heaters[mid + 1]) {
return Math.min(house - heaters[mid], heaters[mid + 1] - house);
} else if (heaters[mid] <= house) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left === 0) return heaters[0] - house;
if (left === heaters.length) return house - heaters[heaters.length - 1];
};
3.4 Heaters Python
class Solution(object):
def findRadius(self, houses, heaters):
houses.sort()
heaters.sort()
N, i, maxRadius = len(heaters), 0, 0
for house in houses:
while i+1 < N and heaters[i+1] < house:
i += 1
maxRadius = max(maxRadius, min([abs(h-house) for h in heaters[i:i+2]]))
return maxRadius
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log n + m log m + n log m) | O(1) |
| Java | O(n log n + m log m + n) | O(1) |
| JavaScript | O(n log n + m log m + n log m) | O(1) |
| Python | O(n log n + m log m + n) | O(1) |
- Binary Search: The C++ and JavaScript implementations explicitly use binary search to find the closest heater, while the Python and Java implementations use a two-pointer approach to achieve the same result.
- Sorting: Sorting the
housesandheatersarrays is a prerequisite for efficient searching, contributing to the O(n log n + m log m) complexity. - Space Efficiency: All implementations are space-efficient, using only the input arrays and a few variables for computation.