475. Heaters - Detailed Explanation
Problem Statement
You are given two integer arrays, houses and heaters. Each element in houses represents the position of a house, and each element in heaters represents the position of a heater, all on a horizontal line. Each heater can warm houses within a certain radius. The goal is to find the minimum radius r such that every house is within distance r of at least one heater.
For example, if you have:
- houses = [1, 2, 3]
- heaters = [2]
Then, the minimum radius needed is 1 because:
- House at 1 is 1 unit away from the heater at 2.
- House at 2 is at the heater.
- House at 3 is 1 unit away from the heater.
The answer in this case is 1.
Detailed Explanation
Key Ideas
-
Sorting:
Since both houses and heaters are given as positions on a line, sorting them helps efficiently determine the closest heater for each house. -
Finding the Closest Heater:
For each house, you need to find the heater that is closest to it. Since the heaters are sorted, you can use binary search to find the position where the house would be inserted in the heaters array.- If the house is exactly at a heater's position, the distance is 0.
- Otherwise, the closest heater is either the one immediately to the left or immediately to the right of the insertion point.
-
Computing the Required Radius:
The required radius r must be large enough so that every house is within distance r of at least one heater. This means you need to calculate the minimum distance from each house to a heater and then take the maximum of these distances.- For each house, compute:
left_distance: Distance from the house to the heater immediately to its left (if it exists).right_distance: Distance from the house to the heater immediately to its right (if it exists).
- The minimum distance for that house is
min(left_distance, right_distance). - The answer is the maximum of these minimum distances across all houses.
- For each house, compute:
Algorithm Steps
-
Sort the Arrays:
Sort both houses and heaters. -
For Each House:
-
Use binary search to find the correct insertion index for the house in the sorted heaters array.
-
Determine the distance to the heater just before this index (if exists) and the heater at this index (if exists).
-
The minimum of these two distances is the distance for the current house to its nearest heater.
-
-
Compute the Answer:
The answer is the maximum of these distances for all houses.
Complexity Analysis
-
Time Complexity:
Sorting takes O(n log n) for houses and O(m log m) for heaters (where n and m are the lengths of the respective arrays). Then, for each house, a binary search on heaters takes O(log m). Overall, the complexity is O(n log m + n log n + m log m). -
Space Complexity:
O(1) additional space (ignoring the space used to store the input arrays).
Python Code
Java Code
Edge Cases
-
Single House or Single Heater:
- When there is only one house and/or one heater, the solution should correctly compute the distance. For example, if there’s one house at position 5 and one heater at position 10, the answer is |10 - 5| = 5.
-
Houses at the Same Position:
- Multiple houses located at the same coordinate should all be considered. The algorithm must compute the distance for that position only once and use it for all houses at that location.
-
Heaters Covering All Houses:
- If every house coincides with a heater (or is extremely close to one), the required radius might be 0 or very small.
-
Houses All on One Side of All Heaters:
- If all houses are positioned to the left of all heaters or vice versa, the distance for each house will be determined solely by the closest extreme heater.
-
Duplicate Heater Positions:
- When multiple heaters are at the same position, the solution should still find the correct closest distance without counting duplicates incorrectly.
Common Mistakes
-
Not Sorting the Arrays:
- Both the houses and heaters arrays must be sorted before performing binary search. Failing to sort can lead to incorrect results because the binary search assumes sorted order.
-
Improper Handling of Binary Search Insertion Point:
- When using binary search, if the house is not exactly found in the heaters array, the insertion point must be correctly interpreted (usually as
-insertionPoint - 1in Java) to determine the nearest heater.
- When using binary search, if the house is not exactly found in the heaters array, the insertion point must be correctly interpreted (usually as
-
Off-by-One Errors:
- Mismanaging the boundaries when checking the heater to the left or right of the insertion point can result in an off-by-one error, leading to an incorrect distance calculation.
-
Ignoring Edge Conditions:
- Not properly handling the cases when the house is before the first heater or after the last heater may result in index errors or incorrect distance computations.
-
Inefficient Linear Search:
- Using a linear search instead of binary search for each house increases the time complexity unnecessarily. Make sure to use binary search to achieve the optimal performance.
Related LeetCode Problems
-
Split Array Largest Sum (LeetCode 410):
Also involves binary search on the answer to minimize the largest sum among subarrays, which is conceptually similar in terms of finding an optimal threshold. -
Koko Eating Bananas (LeetCode 875):
Similar in that it uses binary search on the answer (searching for the minimum time required given a constraint), which is a common technique for optimization problems. -
Capacity To Ship Packages Within D Days (LeetCode 1011):
Another binary search on the answer problem, where the goal is to find the minimum shipping capacity required to ship packages within a certain time frame.
GET YOUR FREE
Coding Questions Catalog
