algoadvance

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.

Every house can be warmed, as long as the house is within the heater’s warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that all houses could be covered by those heaters.

Input:

• Two integer arrays houses and heaters, where houses[i] is the position of the i-th house and heaters[j] is the position of the j-th heater.

Output:

• The minimum radius necessary for all the houses to be covered.

Example 1:

• Input: houses = [1,2,3], heaters = [2]
• Output: 1
• Explanation: The only heater is placed at position 2. The minimum radius to cover all houses is 1.

Example 2:

• Input: houses = [1,2,3,4], heaters = [1,4]
• Output: 1
• Explanation: The two heaters are placed at positions 1 and 4. The minimum radius to cover all houses is 1.

Clarifying Questions

1. Q: Are the positions of the houses and heaters sorted?
   • A: No, the positions are not guaranteed to be sorted.
2. Q: Can there be multiple houses and heaters at the same position?
   • A: Yes, multiple houses and heaters can be at the same position.
3. Q: Can the arrays be empty?
   • A: The problem specification assumes at least one house and one heater.

Strategy

To solve this problem, we need to find the minimum radius required to cover all houses with the given heaters. The plan is:

1. Sort both houses and heaters arrays for easier calculation.
2. For each house, find the heater closest to it.
3. Calculate the distance from the house to the closest heater.
4. The needed radius is the maximum of all these minimum distances.

Algorithm:

1. Sort the houses and heaters arrays.
2. For each house, use binary search to find the position where the heater should be (or the closest ones).
3. Compute the distance to the nearest heater for each house.
4. Return the maximum distance among these minimum distances.

Code

import bisect

def findRadius(houses, heaters):
    houses.sort()
    heaters.sort()
    radius = 0
    
    for house in houses:
        # Use binary search to find the closest heater
        pos = bisect.bisect_left(heaters, house)
        
        # Calculate distances to the closest heaters
        if pos == 0:
            closest_heater_distance = abs(heaters[pos] - house)
        elif pos == len(heaters):
            closest_heater_distance = abs(heaters[-1] - house)
        else:
            closest_heater_distance = min(abs(heaters[pos] - house), abs(heaters[pos - 1] - house))
        
        # Update the radius
        radius = max(radius, closest_heater_distance)
    
    return radius

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

houses = [1,2,3,4]
heaters = [1,4]
print(findRadius(houses, heaters))  # Output: 1

Time Complexity

• Sorting houses and heaters takes (O(n \log n)) and (O(m \log m)), respectively, where (n) is the number of houses and (m) is the number of heaters.
• For each house, binary search takes (O(\log m)).
• Hence, the overall time complexity is (O(n \log n + m \log m + n \log m) = O((n + m) \log (n + m))).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?