345. Heater Reach
Houses and heaters stand along a straight street. The arrays houses and heaters hold the positions of the houses and of the heaters, in any order, and positions may repeat. Every heater warms all houses within the same radius r on either side of it.
Return the smallest whole radius r so that every house is warmed by at least one heater, which means that the distance from every house to its nearest heater is at most r. Checking all heaters for each house takes O(n * m) time, which is too slow for a hundred thousand houses and heaters, so look for the nearest heater faster.
Example 1
- Input:
- houses = [1,5,9], heaters = [4]
- Output:
- 5
- Explanation:
The single heater at 4 is 3, 1 and 5 away from the houses at 1, 5 and 9. The farthest house decides, so the radius is 5.
Example 2
- Input:
- houses = [2,8,14], heaters = [12,3]
- Output:
- 4
- Explanation:
House 2 is 1 from heater 3, house 8 is 4 from heater 12 (and 5 from heater 3), and house 14 is 2 from heater 12. The largest of these nearest distances is 4.
Constraints
1 ≤ houses.length, heaters.length ≤ 105
0 ≤ houses[i], heaters[j] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O((n + m) log m)
- Space
- O(1) extra, or O(m) for sorting