Heaters — LeetCode 475 Python Solution
MediumArrayTwo PointersBinary SearchSorting
- Problem
- #475
- Pattern
- Two Pointers
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
Python
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 leftComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) (after optional sort O(n log n)) |
| Space | O(1) auxiliary |
Pattern: Two Pointers
Use the order already in the input to discard half the search space at every step. LeetCode 475. Heaters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.
The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.
Related problems
LeetCode 658Find K Closest ElementsMediumLeetCode 719Find K-th Smallest Pair DistanceHardLeetCode 786K-th Smallest Prime FractionMediumLeetCode 825Friends Of Appropriate AgesMediumLeetCode 1385Find the Distance Value Between Two ArraysEasyLeetCode 1498Number of Subsequences That Satisfy the Given Sum ConditionMedium
Frequently asked questions
- How hard is LeetCode 475. Heaters?
- LeetCode 475. Heaters is rated Medium on LeetCode.
- What is the time complexity of LeetCode 475. Heaters?
- The Python solution on this page runs in O(n) (after optional sort O(n log n)).
- What is the space complexity of LeetCode 475. Heaters?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 475. Heaters cover?
- LeetCode 475. Heaters is tagged Array, Two Pointers, Binary Search and Sorting on LeetCode.