Problem Statement

The problem asks to find the minimum radius of heaters required to warm all houses on a horizontal line. Each heater has a fixed warm radius, and a house is warmed if it's within the radius of any heater.

Approach

The optimal approach involves sorting both the houses and heaters arrays. Then, for each house, we find the closest heater using binary search (or a linear scan in a simpler implementation). The maximum distance between a house and its closest heater determines the minimum radius required.

The solution can be broken down into the following steps:

1. Sort: Sort the houses and heaters arrays. This allows for efficient searching of the nearest heater for each house.

2. Binary Search (or Linear Scan): For each house, find the closest heater. Binary search offers logarithmic time complexity, improving overall efficiency. If you don't want to implement binary search, a linear scan will work, but the overall complexity will be higher.

3. Calculate Maximum Distance: Keep track of the maximum distance found between a house and its closest heater. This distance represents the minimum radius needed to warm all houses.

Time and Space Complexity Analysis

Time Complexity:

• Sorting: O(M log M + N log N), where M is the number of houses and N is the number of heaters.
• Binary Search (or Linear Scan): O(M log N) using binary search, or O(M*N) using linear scan.

Overall Time Complexity: O(M log M + N log N + M log N) which simplifies to O(M log N) since sorting is typically less than the search, or O(M*N) for linear scan.

Space Complexity:

• Sorting: O(1) in-place sorting is possible, so this is effectively constant space.
• Binary Search (or Linear Scan): O(1) — the algorithm operates with a few pointers and variables.

Overall Space Complexity: O(1)

Code Implementation with Explanations

Here's the code implementation in Python and Java, along with detailed explanations:

Python:

import bisect
 
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        houses.sort()
        heaters.sort()
        max_dist = 0
        
        for house in houses:
            # Binary search to find the closest heater
            idx = bisect.bisect_left(heaters, house)
            
            # Closest heater to the left
            left_dist = float('inf') if idx == 0 else house - heaters[idx-1]
            
            # Closest heater to the right
            right_dist = float('inf') if idx == len(heaters) else heaters[idx] - house
            
            # Update max distance
            max_dist = max(max_dist, min(left_dist, right_dist))
        return max_dist

Explanation:

• bisect.bisect_left(heaters, house) efficiently finds the insertion point of house in the sorted heaters array. This is the index where house would be inserted to maintain the sorted order.
• left_dist and right_dist calculate distances to the closest heaters on the left and right, handling edge cases (first and last heater).
• max_dist tracks the maximum distance encountered.

Java:

import java.util.Arrays;
 
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int maxDist = 0;
        int i = 0;
        for (int house : houses) {
            while (i + 1 < heaters.length && Math.abs(house - heaters[i + 1]) <= Math.abs(house - heaters[i])) {
                i++;
            }
            maxDist = Math.max(maxDist, Math.abs(house - heaters[i]));
        }
        return maxDist;
    }
}

Explanation:

• Arrays.sort() sorts both arrays.
• The loop iterates through houses. The inner while loop efficiently finds the closest heater by comparing distances to the next heater to the current one.
• maxDist keeps track of the largest distance found.

This approach efficiently finds the minimum radius required, leveraging the efficiency of sorting and binary search (or a linear scan if you prefer). The provided code examples offer a clear and concise implementation of this solution.