grid47 Exploring patterns and algorithms
Sep 20, 2024
6 min read
Solution to LeetCode 475: Heaters Problem
You are given the positions of houses and heaters along a horizontal line. Your task is to find the minimum radius required for the heaters so that all houses are within the heater’s warm radius.
Problem
Approach
Steps
Complexity
Input: The input consists of two arrays: `houses` representing the positions of the houses and `heaters` representing the positions of the heaters.
Example: houses = [2, 5, 7, 10], heaters = [1, 8]
Constraints:
• 1 <= houses.length, heaters.length <= 3 * 10^4
• 1 <= houses[i], heaters[i] <= 10^9
Output: Return the minimum radius required for the heaters to cover all houses.
Example: Output: 3
Constraints:
• The output should be an integer representing the minimum radius for heaters.
Goal: Find the minimum radius required for heaters to ensure all houses are covered.
Steps:
• 1. Sort the positions of both the houses and the heaters.
• 2. For each house, calculate the nearest heater and determine the distance between them.
• 3. The largest distance across all houses will determine the required radius of the heaters.
Goal: The constraints are based on the number of houses, heaters, and their positions.
Steps:
• The length of the `houses` and `heaters` arrays is between 1 and 30,000.
• The positions of the houses and heaters range between 1 and 10^9.
Assumptions:
• The heaters can be placed at any position along the horizontal line.
• There is no overlap in the positions of houses and heaters.
• Input: houses = [2, 5, 7, 10], heaters = [1, 8]
• Explanation: Heaters at positions 1 and 8 with a radius of 3 can cover all the houses.
• Input: houses = [5, 10], heaters = [6]
• Explanation: A heater at position 6 with a radius of 4 can cover both houses at positions 5 and 10.
Approach: The approach involves sorting the house and heater positions, then calculating the minimum required radius by comparing distances.
Observations:
• Sorting the houses and heaters simplifies the task of finding the nearest heater for each house.
• A greedy approach that evaluates the closest heater to each house would be efficient.
• By calculating the distance from each house to its nearest heater, we can determine the minimum radius required for coverage.
Steps:
• 1. Sort the `houses` and `heaters` arrays.
• 2. For each house, use a two-pointer or binary search approach to find the nearest heater.
• 3. Track the largest distance to the nearest heater, which will be the required minimum radius.
Empty Inputs:
• There will always be at least one house and one heater, as per the constraints.
Large Inputs:
• Handle cases where the number of houses or heaters is large (up to 30,000).
Special Values:
• Consider cases where all heaters are clustered in one area or spread across a wide range.
Constraints:
• Ensure the solution works efficiently within the constraints of up to 30,000 houses and heaters.
intfindRadius(vector<int>& home, vector<int>& warm) {
sort(home.begin(), home.end());
sort(warm.begin(), warm.end());
int m = home.size(), n = warm.size();
vector<int> res(m, INT_MAX);
for(int h =0, w =0; h < m && w < n; ) {
if (home[h] <= warm[w]) {
res[h] = warm[w] - home[h];
h++;
} else w++;
}
for(int h = m -1, w = n -1; h >=0&& w >=0; ) {
if (home[h] >= warm[w]) {
res[h] = min(res[h], home[h] - warm[w]);
h--;
} else w--;
}
return*max_element(res.begin(), res.end());
}
Defines the `findRadius` function, which takes two vectors, `home` and `warm`, representing the positions of homes and warm heaters, and returns the minimum radius required to ensure every home is covered.
2 : Sorting
sort(home.begin(), home.end());
Sorts the `home` vector to facilitate the process of finding the closest heater for each home.
3 : Sorting
sort(warm.begin(), warm.end());
Sorts the `warm` vector to make it easier to check the closest heater to a given home.
4 : Variable Initialization
int m = home.size(), n = warm.size();
Initializes `m` as the number of homes and `n` as the number of heaters.
5 : Vector Initialization
vector<int> res(m, INT_MAX);
Initializes a vector `res` of size `m` (the number of homes), setting each element to `INT_MAX` as an initial placeholder for the minimum distances to the closest heater.
6 : Left to Right Sweep
for(int h =0, w =0; h < m && w < n; ) {
Begins a loop that iterates over both homes (`h`) and heaters (`w`) from left to right to compute the closest heater to each home.
7 : Condition Check
if (home[h] <= warm[w]) {
Checks if the current home is to the left of or at the current heater position.
8 : Update Distance
res[h] = warm[w] - home[h];
Updates the minimum distance for home `h` to the current heater `w`.
9 : Increment Home Pointer
h++;
Increments the home pointer `h` to consider the next home.
10 : Increment Heater Pointer
} else w++;
If the current home is not covered by the current heater, increments the heater pointer `w` to check the next heater.
11 : Right to Left Sweep
for(int h = m -1, w = n -1; h >=0&& w >=0; ) {
Begins a loop that iterates over both homes (`h`) and heaters (`w`) from right to left to compute the closest heater to each home in the reverse direction.
12 : Condition Check
if (home[h] >= warm[w]) {
Checks if the current home is to the right of or at the current heater position.
13 : Update Distance
res[h] = min(res[h], home[h] - warm[w]);
Updates the minimum distance for home `h` by considering the current heater `w` and taking the minimum between the previous calculated distance and the new one.
14 : Decrement Home Pointer
h--;
Decrements the home pointer `h` to consider the next home in the reverse direction.
15 : Decrement Heater Pointer
} else w--;
If the current home is not covered by the current heater, decrements the heater pointer `w` to check the next heater in the reverse direction.
16 : Final Calculation
return*max_element(res.begin(), res.end());
Returns the maximum value from the `res` vector, which represents the largest of the minimum distances to the closest heater for all homes.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: Sorting the houses and heaters requires O(n log n) time, where n is the number of houses or heaters.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for sorting the arrays.
