AC Java solution with Binary Search

• The idea is to use binary search to find the proper radius. Note that the minimum is 0 (rather than 1), and the maximum is Math.max(houses[house_num-1], heaters[heater_num-1]) - Math.min(houses[0], heaters[0]), since some heaters may be beyond rightmost houses.

Then for each middle radius, check whether it is a valid radius. If it's not, then min = mid+1. Otherwise, to check whether middle radius is the minimum one.

'''
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);

``````    int house_num = houses.length;
int heater_num = heaters.length;
int min = 0;
int max = Math.max(houses[house_num-1], heaters[heater_num-1]) - Math.min(houses[0], heaters[0]);
while(min<=max){
int mid = min + (max-min)/2;
boolean fit = check(houses, heaters, mid);
if(fit==false){
min = mid+1;
}else{  //mid is a good fit
if(min==mid){
return mid;
}else{
max = mid;
}
}
}
return min;
}

private boolean check(int[] houses, int[] heaters, int r){
int house_num = houses.length;
int heater_num = heaters.length;
int i = 0, j = 0;

while(i<heater_num){
int left = Math.max(heaters[i]-r,houses[0]);
int right = Math.min(heaters[i]+r,houses[house_num-1]);
while(j<house_num){
if(houses[j]<left) return false;
else if(houses[j]<=right){
j++;
}else{
break;
}
}
i++;
}
if(j<house_num) return false;
return true;
}
``````

}
'''

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.