Java (m+n) solution 18ms


  • -1
    Y
    public int findRadius(int[] houses, int[] heaters) {
        int hl = houses.length;
        if(hl ==0 || heaters.length==0)
            return 0;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ret=0;
        for(int i=0,j=0; i<hl;i++){
            while(j<heaters.length && houses[i]>heaters[j])
                j++;
            if(j==heaters.length)                                 // no more heater
                return Math.max(ret,Math.max(Math.abs(houses[i]-heaters[j-1]), Math.abs(houses[hl-1]-heaters[j-1])));
            else                                                  //1st time, house is on the heater left
                 if(j-1>=0)                                       //is 1st heater that is greater than it
                     ret=Math.max(ret,Math.min(houses[i]-heaters[j-1],heaters[j]-houses[i]));
                 else    
                     ret=Math.max(ret,heaters[j]-houses[i]);
        }
        return ret;
    }

Log in to reply
 

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