algoadvance

Leetcode 475. Heaters

Problem Statement

Winter is coming! During the contest, your first job is to design a standard heater with 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.

Note:

  1. All the heaters follow your radius standard, and the warm radius will be the same.
  2. Snowdrops are numbered at houses and heater positions are given in heaters.
  3. Both houses and heaters are non-empty arrays and contain only positive integers.
  4. Each position is a non-negative integer.

Example 1:

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

Example 2:

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters are placed in the positions 1 and 4. We need to take the radius about 1 for all the houses to be warmed.

Example 3:

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

Clarifying Questions

  1. Are houses and heaters already sorted?
    • No, we should not assume they are sorted.
  2. Is it guaranteed that there will be at least one heater and one house?
    • Yes, both arrays are non-empty as mentioned in the problem statement.

Strategy

  1. Sort Both Arrays: We start by sorting the arrays of house positions and heater positions.
  2. Binary Search for Closest Heater: For each house, perform a binary search to find the closest heater and calculate the distance.
  3. Maximum Minimum Distance: Track the maximum of these minimum distances (this will be our required radius).

Code

import java.util.Arrays;

public class Heaters {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int radius = 0;

        for (int house : houses) {
            int closestHeaterDistance = findClosestHeaterDistance(house, heaters);
            radius = Math.max(radius, closestHeaterDistance);
        }

        return radius;
    }

    private int findClosestHeaterDistance(int house, int[] heaters) {
        int left = 0, right = heaters.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (heaters[mid] == house) {
                return 0;
            } else if (heaters[mid] < house) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        int dist1 = (left < heaters.length) ? Math.abs(heaters[left] - house) : Integer.MAX_VALUE;
        int dist2 = (right >= 0) ? Math.abs(heaters[right] - house) : Integer.MAX_VALUE;

        return Math.min(dist1, dist2);
    }

    public static void main(String[] args) {
        Heaters heaters = new Heaters();
        
        int[] houses1 = {1, 2, 3};
        int[] heater1 = {2};
        System.out.println(heaters.findRadius(houses1, heater1));  // Output: 1
        
        int[] houses2 = {1, 2, 3, 4};
        int[] heater2 = {1, 4};
        System.out.println(heaters.findRadius(houses2, heater2));  // Output: 1
        
        int[] houses3 = {1, 5};
        int[] heater3 = {2};
        System.out.println(heaters.findRadius(houses3, heater3));  // Output: 3
    }
}

Time Complexity

  1. Sorting: Sorting houses and heaters both take O(n log n + m log m), where n is the number of houses and m is the number of heaters.
  2. Binary Search: For each house, binary search in heaters array takes O(log m). If you do this for all houses, it will be O(n log m).

Thus, the overall time complexity is O(n log n + m log m + n log m) which simplifies to O((n + m) log (n + m)) since typically both arrays need to be sorted, and then all houses are checked against heaters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI