AC Java solution with Binary Search


  • 0
    S

    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;
    }
    

    }
    '''


Log in to reply
 

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