heaters [Binary search]

XXX. Heaters

Binary Search

Greedy

Problem Statement:

You are given an array houses representing the positions of houses and heaters representing the positions of heaters. Each heater can warm the closest houses to its position. Return the minimum radius of heat coverage so that all houses are covered.

Example:

Input:

            houses = [1, 2, 3], heaters = [2]
        

Output:

1

Explanation: The heater at position 2 covers houses 1, 2, and 3 with a radius of 1.

Approach:

1. Sort the heaters array to enable binary search.
2. For each house, calculate the minimum distance to the nearest heater using binary search.
3. Track the maximum of these minimum distances, which will be the required radius.

Algorithm Intuition:

The key is to find the closest heater for each house. By sorting the heaters array, binary search helps efficiently determine the nearest heater for a house. The radius must be large enough to cover the house that is farthest from its nearest heater.

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), as we use constant additional space.

Java Implementation:

public int findRadius(int[] houses, int[] heaters) {
    int minRadius = Integer.MIN_VALUE;

    // Sort heaters to enable binary search
    Arrays.sort(heaters);

    // For each house, find the distance to the nearest heater
    for (int house : houses) {
        int minDistance = binarySearch(heaters, house);
        minRadius = Math.max(minRadius, minDistance); // Track maximum of minimum distances
    }

    return minRadius; // This will be the required radius
}

public int binarySearch(int[] heaters, int house) {
    int low = 0, high = heaters.length - 1;

    // Binary search for the closest heater
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (house < heaters[mid]) high = mid - 1;
        else if (house > heaters[mid]) low = mid + 1;
        else return 0; // Exact match: house is at heater
    }

    // Determine the minimum distance from the closest heaters
    low = low <= heaters.length - 1 ? low : heaters.length - 1; // Clamp low to valid index
    high = high >= 0 ? high : 0; // Clamp high to valid index

    int d1 = Math.abs(house - heaters[low]); // Distance to the heater at index low
    int d2 = Math.abs(house - heaters[high]); // Distance to the heater at index high

    return Math.min(d1, d2); // Return the smallest distance
}