Heaters - Leetcode Solution

Problem:

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 a point on the x-axis, and the warmth of the heater with a fixed warm radius x reaches all houses x - radius <= house <= x + radius.

The task is to cover every house in the shortest number of heaters.

Example 1:

Input: houses = [1,2,3], heaters = [2] Output: 1 Explanation: The only heater was placed in the position 2, and all the houses were warmed.

Example 2:

Input: houses = [1,3,2], heaters = [2] Output: 1 Explanation: The only heater was placed in the position 2, and all the houses were warmed.

Example 3:

Input: houses = [1,2,3,4], heaters = [1,4] Output: 1 Explanation: The two heaters were placed in the positions 1 and 4. All the houses were warmed.

Approach:

The given problem can be solved using a two-pointer approach. We can sort the heaters and the houses arrays and loop through each house to find the closest heater to it. For each house, we can start with either the closest left heater or the closest right heater based on which is closest. We keep track of the distance between the house and the closest heater and update the maximum distance found so far. We then move the pointer of the closest heater to the right if the house is to the right of it and to the left if the house is to the left of it. We repeat this process for all houses and return the maximum distance found as the answer.

Steps:

1. Sort the houses and heaters arrays.

2. Initialize two pointers i and j to 0 to point to the first element of the houses and heaters arrays, respectively.

3. Initialize a variable maxDist to 0 to store the maximum distance found.

4. Loop through each house:

   a. If the current house is to the left of the current heater, move the current pointer of the heater to the left until the house is not to the left of it.

   b. If the current house is to the right of the current heater, move the current pointer of the heater to the right until the house is not to the right of it.

   c. Calculate the distance between the current house and the current heater.

   d. Update the maxDist variable if the calculated distance is greater than the current maxDist.

5. Return the maxDist variable as the answer.

Code:

Time Complexity: O(nlogn + mlogm), where n is the length of the houses array and m is the length of the heaters array. The sorting operation takes O(nlogn + mlogm) time, and the loop over each house takes O(n) time.

Space Complexity: O(1). We are not using any extra space except for a few variables.

1