475. Heaters
Model: qwen3.5:9b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 33.7%
Problem Breakdown
We are given two arrays: houses representing locations of houses needing heat, and heaters representing available heating units on the same 1D line. We need to find a single integer radius such that every house is covered by at least one heater within distance . The goal is to minimize this global .
Inputs:
- Two lists of integers:
houses,heaters. - Constraints: Lengths up to 30,000; values up to (large range).
Outputs:
- A single integer representing the minimum required radius.
Implicit Constraints & Edge Cases:
- Inputs are not guaranteed to be sorted initially. Sorting is a prerequisite for efficient search.
- Duplicates in
housesorheaters: Logic remains valid; duplicates don’t change distance calculations but affect array size slightly (handled naturally). - Houses outside the range of heaters: The radius must extend far enough to reach them, which our logic handles by checking neighbors on both sides.
- Overflow: Python handles large integers automatically, so fits without overflow concerns unlike C++/Java
int.
Intuition
A brute-force approach would be to iterate through every house and check the distance against every heater for each one. That results in an complexity where is houses count and is heaters count. With inputs up to 30,000, , which risks Time Limit Exceeded (TLE) in Python or slower languages given typical interview time limits (~5-6 seconds).
We need a faster way to find the “closest heater” for any specific house. Since heaters are fixed points on a line, if we sort them, they form an ordered sequence. For any house position , the closest heater must be either immediately to its left or immediately to its right in the sorted heaters array.
This suggests using Binary Search. If we have a sorted list of heaters, finding the insertion point for a specific house takes . We can do this for every house ( times), resulting in an overall complexity dominated by sorting and binary search steps: , which is well within limits.
Approach
- Sort Heaters: First, sort the
heatersarray to enable binary searching. This takes . We do not need to sort houses because we iterate through them in any order; for each house, we find its optimal heater independently. - Iterate Houses: For every house position:
- Use
bisect_left(binary search) on the sorted heaters array to find the index of the first heater current house position. Let’s call this indexidx.
- Use
- Calculate Local Radius:
- If a valid heater exists at or after
house_pos, calculate distance:heaters[idx] - house. - Check if there is a previous heater (
idx > 0). Calculate distance:house - heaters[idx-1]. - The minimum radius required for this specific house is the smaller of these two distances (or just one if it’s at an edge).
- If a valid heater exists at or after
- Update Global Radius: Keep track of the maximum of all local radii found across every house. This global max represents the bottleneck—the hardest-to-cover house determines the final standard.
- Return Result.
Complexity Analysis
- Time Complexity: . Sorting heaters takes . Iterating through houses ( times) with binary search (
bisect) inside takes . Given constraints, this is roughly operations per list, which is very fast. - Space Complexity: auxiliary space (ignoring the sort stack). We only use a few variables for tracking distances and indices.
Solution
import bisect
from typing import List
def findRadius(houses: List[int], heaters: List[int]) -> int:
# Sort heaters to enable binary search logic
heaters.sort()
max_radius = 0
# Iterate through each house and determine the minimum radius needed for it
for h in houses:
# Find insertion point of current house position in sorted heaters array.
# bisect_left returns index where all elements to left are < h,
# so element at idx is >= h (if exists).
idx = bisect.bisect_left(heaters, h)
min_dist_for_house = float('inf')
# Check heater immediately to the right or equal position
if idx < len(heaters):
min_dist_for_house = heaters[idx] - h
# Check heater immediately to the left (if exists)
if idx > 0:
dist_left = h - heaters[idx-1]
if dist_left < min_dist_for_house:
min_dist_for_house = dist_left
# The global radius must be at least what this house requires
max_radius = max(max_radius, min_dist_for_house)
return max_radius
# Example usage (optional for interview context but good for verification):
# print(findRadius([1, 2, 3], [2])) # Output: 1
# print(findRadius([1, 2, 3, 4], [1, 4])) # Output: 1
Edge Cases Handled
- Single Heater:
bisect_leftreturns index 0 or len. Logic checks both neighbors (one will be out of bounds), correctly picking the single available distance. - House at Exact Heater Position: Distance becomes 0 for that house, which doesn’t increase global max unless another house requires more radius. Correctly handled by subtraction logic resulting in 0.
- Houses Outside Heaters Range:
bisect_leftreturns index beyond array or before start. Logic checks valid neighbors only (e.g., if all heaters are left of house,idx == len, we ignore right neighbor and take distance to last heater). If all heaters are right, similar logic applies via the check atidx > 0. - Large Coordinates: Python handles large integers natively; no overflow occurs during subtraction or comparison.