DSA problem
Heaters
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.
The answer is the smallest radius r such that, for every house, there exists at least one heater within distance r. Equivalently, r is the maximum over all houses of (distance from that house to its closest heater). Once you frame it this way, the algorithm falls out: for each house, find the nearest heater; take the maximum of those nearest distances.
To find the nearest heater to a house in O(log m), sort the heaters once and binary-search the house's position. The two candidates are the heater just to the left (the predecessor) and the heater just to the right (the successor), whichever exists. The closer of the two gives the house's contribution. Sorting takes O(m log m); the per-house lookup is O(log m). Total O((n + m) log m) time and O(1) extra space.
A natural fit for the standard library: bisect.bisect_left in Python, std::lower_bound in C++, or Collections.binarySearch (with manual insertion-point handling) in Java. Edge cases are clean: if the house position is smaller than every heater the only candidate is the leftmost heater; if larger than every heater the only candidate is the rightmost.
Examples
houses = [1,2,3], heaters = [2]1houses = [1,2,3,4], heaters = [1,4]1houses = [1,5], heaters = [2]3Constraints
- 1 <= houses.length, heaters.length <= 3 * 10^4
- 1 <= houses[i], heaters[i] <= 10^9
- houses and heaters are not necessarily sorted on input.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.