Last updated on July 18th, 2024 at 03:23 am

Here, We see Heaters LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Binary-Search

Companies

Google

Level of Question

Medium

Heaters LeetCode Solution

Problem Statement

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

1. Heaters LeetCode Solution C++

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int radius = 0;
        sort(heaters.begin(), heaters.end());
        for(auto house : houses) {
            if(house <= heaters.front()) {
                radius = max(radius, heaters.front() - house);
                continue;
            }
            if(house >= heaters.back()) {
                radius = max(radius, house - heaters.back());
                continue;
            }
            radius = max(radius, findAjacentHeaters(house, heaters));
        }
        return radius;
    }
private:
    int findAjacentHeaters(int house, vector<int>& heaters) {
        int radius = 0;
        int l = 0;
        int r = heaters.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(heaters[mid] == house) return 0;
            if(heaters[mid] < house) l = mid + 1;
            if(heaters[mid] > house) r = mid - 1;
        }
        return min(heaters[l]-house, house-heaters[r]);
    }
};

2. Heaters LeetCode Solution Java

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        if(houses == null || houses.length == 0 || heaters == null || heaters.length == 0){
            return 0;
        }
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int n = houses.length;
        int m = heaters.length; 
        int i = 0;
        int j = 0;
        int res = 0;
        while(i < n && j < m){
            int dist1 = Math.abs(heaters[j] - houses[i]);
            int dist2 = Integer.MAX_VALUE;
            if(j + 1 < m){
                dist2 = Math.abs(heaters[j + 1] - houses[i]);
            }
            if(dist1 < dist2){
                res = Math.max(res, dist1);
                i++;
            }else{
                j++;
            }
        }
        return res;
    }
}

3. Heaters Solution JavaScript

var findRadius = function(houses, heaters) {
  heaters.sort((a, b) => a - b);
  return Math.max(...houses.map(h => findMinDistance(h, heaters)));
};
const findMinDistance = (house, heaters) => {
  let left = 0;
  let right = heaters.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (heaters[mid] <= house && house <= heaters[mid + 1]) {
      return Math.min(house - heaters[mid], heaters[mid + 1] - house);
    } else if (heaters[mid] <= house) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  if (left === 0) return heaters[0] - house;
  if (left === heaters.length) return house - heaters[heaters.length - 1];
};

4. Heaters Solution Python

class Solution(object):
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        N, i, maxRadius = len(heaters), 0, 0
        for house in houses:
            while i+1 < N and heaters[i+1] < house:
                i += 1
            maxRadius = max(maxRadius, min([abs(h-house) for h in heaters[i:i+2]]))    
        return maxRadius