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.
This approach improves upon the brute-force method by first sorting the heaters array. Then, for each house, it uses binary search to efficiently find the closest heater(s) instead of performing a linear scan.
Algorithm
- Sort the
heatersarray. This allows for efficient searching. - Initialize
maxRadiusto 0. - For each
housein thehousesarray:- Use binary search (e.g.,
Arrays.binarySearch) to find the insertion point of thehousein the sortedheatersarray. - The insertion point helps identify the two heaters closest to the current house: one to its left (
heaters[insertion_point - 1]) and one to its right (heaters[insertion_point]). - Calculate the distance to both these heaters. Handle edge cases where the house is before the first heater or after the last one.
- The minimum distance for the current house is the smaller of these two distances.
- Update
maxRadiuswith the maximum distance found so far.
- Use binary search (e.g.,
- Return
maxRadius.
Walkthrough
The core idea is that for any house, its closest heater must be one of the two heaters that 'surround' it in the sorted heaters array. By sorting the heaters, we can use binary search to find these two surrounding heaters in logarithmic time, which is a significant improvement over the linear scan of the brute-force approach. For each house, we find its potential position in the sorted heaters array. If the house position matches a heater's position, the distance is 0. Otherwise, we identify the heaters immediately to the left and right of the house's position and calculate the distance to each. The smaller of these two distances is the minimum required radius for that house. The final answer is the maximum of these minimum radii over all houses.
import java.util.Arrays; class Solution { public int findRadius(int[] houses, int[] heaters) { Arrays.sort(heaters); int result = 0; for (int house : houses) { int index = Arrays.binarySearch(heaters, house); // If house is at a heater location, distance is 0 for this house if (index >= 0) { continue; } // Find insertion point to locate surrounding heaters int insertionPoint = -(index + 1); int dist1 = Integer.MAX_VALUE; // Distance to the heater on the left if (insertionPoint > 0) { dist1 = house - heaters[insertionPoint - 1]; } int dist2 = Integer.MAX_VALUE; // Distance to the heater on the right if (insertionPoint < heaters.length) { dist2 = heaters[insertionPoint] - house; } result = Math.max(result, Math.min(dist1, dist2)); } return result; }}Complexity
Time
O(M log M + N log M), where N is the number of houses and M is the number of heaters. O(M log M) for sorting heaters and O(log M) for the binary search for each of the N houses.
Space
O(log M) or O(M), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses O(log M) space on average.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Efficient when the number of heaters is large.
Cons
Can be slightly less efficient than the two-pointer approach if the number of houses (N) is much larger than the number of heaters (M).
This is a highly efficient approach that involves sorting both the houses and heaters arrays and then using a two-pointer technique to find the minimum radius in a single pass over the sorted arrays.
Algorithm
- Sort both the
housesandheatersarrays. - Initialize
radius = 0, and two pointers,i = 0for houses andj = 0for heaters. - Iterate through each
houseusing pointeri:- For the current
house[i], find the pair of heaters that surround it. Advance the heater pointerjas long as the next heaterheaters[j+1]is closer to or at the same location ashouse[i]. - After finding the best
j, the closest heaters areheaters[j]andheaters[j+1](if it exists). - Calculate the distance to the left heater (
dist1 = |houses[i] - heaters[j]|) and the right heater (dist2, ifheaters[j+1]exists). - The minimum radius needed for
house[i]ismin(dist1, dist2). - Update the overall
radiusto be the maximum of what's needed for all houses seen so far.
- For the current
- Return
radius.
Walkthrough
By sorting both arrays, we can process houses in increasing order of their position. This allows us to find the closest heater for each house without re-scanning the heaters array. We use one pointer for houses (i) and one for heaters (j). As we iterate through the sorted houses, we only need to advance the heater pointer j forward. This is because for the next house houses[i+1], its closest heater cannot be before the closest heater of houses[i]. For each house, we find the two heaters that bracket it, calculate the distance to both, and take the minimum. The final answer is the maximum of these minimums. This avoids the repeated logarithmic searches of the previous approach, replacing it with a single linear scan.
import java.util.Arrays; class Solution { public int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int i = 0; // pointer for houses int j = 0; // pointer for heaters int radius = 0; while (i < houses.length) { // Find the heater that is just left of or at the current house's position while (j + 1 < heaters.length && heaters[j + 1] <= houses[i]) { j++; } // Distance to the heater on the left (or at the same position) int dist1 = Math.abs(houses[i] - heaters[j]); // Distance to the heater on the right int dist2 = Integer.MAX_VALUE; if (j + 1 < heaters.length) { dist2 = heaters[j + 1] - houses[i]; } // The required radius for this house is the minimum of the two distances int currentRadius = Math.min(dist1, dist2); // The overall radius must be large enough for all houses radius = Math.max(radius, currentRadius); i++; } return radius; }}Complexity
Time
O(N log N + M log M), dominated by the sorting of the two arrays. The subsequent two-pointer scan is O(N + M), which is faster than the main sorting step.
Space
O(log N + log M) or O(N + M), depending on the space used by the sorting algorithm.
Trade-offs
Pros
Very efficient, typically the fastest approach in practice due to the linear scan after sorting.
Optimal time complexity for a comparison-based solution.
Cons
Requires modifying the input arrays by sorting them, or creating sorted copies which would increase space 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; }}class Solution {public: int findRadius(vector<int> &houses, vector<int> &heaters) { sort(houses.begin(), houses.end()); sort(heaters.begin(), heaters.end()); int left = 0, right = 1e9; while (left < right) { int mid = left + right >> 1; if (check(houses, heaters, mid)) right = mid; else left = mid + 1; } return left; } bool check(vector<int> &houses, vector<int> &heaters, int r) { int m = houses.size(), n = heaters.size(); int i = 0, j = 0; while (i < m) { if (j >= n) return false; int mi = heaters[j] - r; int mx = heaters[j] + r; if (houses[i] < mi) return false; if (houses[i] > mx) ++j; else ++i; } return true; }};class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -> int: houses . sort() heaters . sort() def check(r): m, n = len(houses), len(heaters) i = j = 0 while i < m: if j >= n: return False mi = heaters[j] - r mx = heaters[j] + r if houses[i] < mi: return False if houses[i] > mx: j += 1 else: i += 1 return True left, right = 0, int(1e9) while left < right: mid = (left + right) >> 1 if check(mid): right = mid else: left = mid + 1 return leftVideo 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.