LeetCode Solutions Blog

Heaters

Number: 475

Difficulty: Medium

Paid? No

Problem Description

Given positions of houses and heaters on a horizontal line, determine the minimum radius standard for all heaters such that every house is within the warm radius of at least one heater.

Key Insights

Sort both the houses and the heaters arrays to efficiently search for the nearest heater for any given house.
For each house, use binary search to locate the heater that is closest.
The minimum required radius is the maximum distance a house is from its nearest heater.
The problem leverages binary search for each house, leading to an overall efficient solution.

Space and Time Complexity

Time Complexity: O(n log m) where n is the number of houses and m is the number of heaters. Space Complexity: O(1) (ignoring the space required for input sorting, which can be done in-place)

Solution

The solution first sorts the houses and heaters arrays. For each house, binary search is applied to the heaters array to find the position where the heater value is just greater than or equal to the house's position. The distance to the closest heater is then the minimum of the distance from the house to the heater just before or just after this position. Finally, the answer is the maximum of these minimum distances, ensuring that every house is within the coverage of some heater.

Code Solutions

# Function to compute the minimum radius required for heaters to warm all houses
def findRadius(houses, heaters):
    # Sort both arrays for efficient searching
    houses.sort()  # O(n log n)
    heaters.sort()  # O(m log m)
    
    radius = 0
    # Iterate over each house and find the nearest heater using binary search
    for house in houses:
        low, high = 0, len(heaters) - 1
        # Binary search to find the right position in heaters array
        while low <= high:
            mid = (low + high) // 2
            if heaters[mid] < house:
                low = mid + 1
            else:
                high = mid - 1
        # low is the index of the first heater >= house (if exists)
        # high is the index of the last heater <= house (if exists)
        left_dist = abs(house - heaters[high]) if high >= 0 else float('inf')
        right_dist = abs(heaters[low] - house) if low < len(heaters) else float('inf')
        nearest = min(left_dist, right_dist)
        radius = max(radius, nearest)
    return radius

# Example usage:
houses = [1,5]
heaters = [2]
print(findRadius(houses, heaters))  # Expected Output: 3