We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Heaters

Difficulty: Medium

Problem Description

Given the positions of houses and heaters on a horizontal line, return the minimum radius of heaters needed to warm all houses. A house can be warmed if it is within the heater's warm radius range.

Key Insights

  • Each heater can warm houses that are within a certain distance (radius).
  • The goal is to find the smallest radius that ensures all houses are covered by at least one heater.
  • Sorting the positions of both houses and heaters simplifies the problem, allowing for efficient searching.

Space and Time Complexity

Time Complexity: O(N log N + M log M) where N is the number of houses and M is the number of heaters (due to sorting). Space Complexity: O(1) as we are using constant extra space.

Solution

To solve the problem, we can follow these steps:

  1. Sort the array of houses and the array of heaters.
  2. For each house, use binary search to find the closest heater.
  3. Calculate the distance between the house and the closest heater to determine the required radius for that house.
  4. The answer will be the maximum of these distances, which will ensure all houses are covered.

The algorithm utilizes sorting and binary search for efficient lookup, making it suitable for large input sizes.

Code Solutions

def findRadius(houses, heaters):
    houses.sort()
    heaters.sort()
    
    def findClosestHeater(house):
        left, right = 0, len(heaters) - 1
        while left < right:
            mid = (left + right) // 2
            if heaters[mid] < house:
                left = mid + 1
            else:
                right = mid
        return left
    
    radius = 0
    for house in houses:
        idx = findClosestHeater(house)
        closest_distance = float('inf')
        
        if idx < len(heaters):
            closest_distance = abs(heaters[idx] - house)
        if idx > 0:
            closest_distance = min(closest_distance, abs(heaters[idx - 1] - house))
        
        radius = max(radius, closest_distance)
    
    return radius
← Back to All Questions