Heaters
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each house and, for every house, finds the minimum distance to any of the heaters by checking all of them. The final answer is the maximum of these minimum distances found for each house.
Algorithm
- Initialize a variable
maxRadiusto 0. - For each
housein thehousesarray:- Initialize
minDistForHouseto a very large value (infinity). - For each
heaterin theheatersarray:- Calculate the absolute difference
dist = |house - heater|. - Update
minDistForHouse = min(minDistForHouse, dist).
- Calculate the absolute difference
- After checking all heaters for the current house, update
maxRadius = max(maxRadius, minDistForHouse).
- Initialize
- Return
maxRadius.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. The logic is to simulate the process directly. For every single house, we need to find which heater is closest to it. To do this, we can compare its position with every heater's position, calculate the distance, and keep track of the minimum one. After finding the minimum distance for a house, we know that the final radius must be at least this large to cover it. We repeat this for all houses and take the maximum of all these minimum distances, as this maximum value will be the smallest radius that is guaranteed to cover every house.
class Solution { public int findRadius(int[] houses, int[] heaters) { int maxRadius = 0; for (int house : houses) { int minDistance = Integer.MAX_VALUE; for (int heater : heaters) { minDistance = Math.min(minDistance, Math.abs(house - heater)); } maxRadius = Math.max(maxRadius, minDistance); } return maxRadius; }}Complexity
Time
O(N * M), where N is the number of houses and M is the number of heaters. This is because for each of the N houses, we iterate through all M heaters.
Space
O(1), as we only use a few variables to store intermediate results, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs due to its quadratic time complexity.
Solutions
Solution
class Solution {public int findRadius(int[] houses, int[] heaters) { Arrays.sort(heaters); int res = 0; for (int x : houses) { int i = Arrays.binarySearch(heaters, x); if (i < 0) { i = ~i; } int dis1 = i > 0 ? x - heaters[i - 1] : Integer.MAX_VALUE; int dis2 = i < heaters.length ? heaters[i] - x : Integer.MAX_VALUE; res = Math.max(res, Math.min(dis1, dis2)); } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.