475. Heaters | zhengxingxing

Method 1

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 those heaters could cover all houses.**
Notice that all the heaters follow your radius standard, and the warm radius will the same.

Example 1

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Example 3

Input: houses = [1,5], heaters = [2]
Output: 3

Method 1

【O(nlogm) time | O(1) space】

package Leetcode.BinarySearch.FindMinimum;

import java.util.Arrays;

/**
 * @author zhengxingxing
 * @date 2025/04/30
 */
public class Heaters {
    public static int findRadius(int[] houses, int[] heaters) {
        // Sort heaters array to enable binary search
        Arrays.sort(heaters);

        // Initialize the maximum radius needed
        int maxRadius = 0;

        // Iterate through each house to find its minimum heating radius
        for (int house: houses) {
            // Use binary search to find the insertion point for current house
            int index = Arrays.binarySearch(heaters, house);

            // If house position has a heater, no need to calculate distance
            if (index >= 0){
                continue;
            }

            // Convert negative insertion point to actual index
            // If binary search returns -x, the actual insertion point is (x-1)
            index = -(index + 1);

            // Calculate distances to nearest heaters:
            // dist1: distance to heater on the left (if exists)
            // If no heater on left (index-1 < 0), set to MAX_VALUE
            int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;

            // dist2: distance to heater on the right (if exists)
            // If no heater on right (index >= length), set to MAX_VALUE
            int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;

            // Update maximum radius needed:
            // Take minimum of dist1 and dist2 (nearest heater)
            // Take maximum with previous maxRadius (need to cover all houses)
            maxRadius = Math.max(maxRadius, Math.min(dist1, dist2));
        }

        return maxRadius;
    }
    
    public static void main(String[] args) {
        // Test Case 1: Houses at positions 1,2,3 with heater at position 2
        // Expected result: 1 (radius of 1 can cover all houses)
        int[] houses1 = {1, 2, 3};
        int[] heaters1 = {2};
        System.out.println("Test Case 1 Result: " + findRadius(houses1, heaters1));

        // Test Case 2: Houses at positions 1,2,3,4 with heaters at positions 1,4
        // Expected result: 1 (heater at 1 covers houses 1,2; heater at 4 covers houses 3,4)
        int[] houses2 = {1, 2, 3, 4};
        int[] heaters2 = {1, 4};
        System.out.println("Test Case 2 Result: " + findRadius(houses2, heaters2));

        // Test Case 3: Houses at positions 1,5 with heater at position 2
        // Expected result: 3 (need radius of 3 to cover both houses from position 2)
        int[] houses3 = {1, 5};
        int[] heaters3 = {2};
        System.out.println("Test Case 3 Result: " + findRadius(houses3, heaters3));
    }
}

Method 1

Enjoy Reading This Article?