9 lines O(len of houses) + O(len of heaters) Greedy Java Solution


  • 0
    Y
    public int findRadius(int[] houses, int[] heaters) {
            int rh = 0;
            int radius = 0;
            Arrays.sort(houses);
            Arrays.sort(heaters);
            
            for(int hs: houses){
                
                //find the first heater located right of that houses
                while(rh < heaters.length  && hs > heaters[rh]) rh++;
                
                //the house (hs) has to be covered by either the heater left to it (lh) or right to it (rh)
                //If the house is closer to lh, it requires lh has a "local" radius of hs - lh
                //If the house is closer to rh, it requires rh has a "local" radius of rh - hs
                //whichever heater the "local" radius attributes to, it increases requirement on the global heater radius
                //which is the max of all heaters radius required "locally"
                int r = Math.min(rh==0? Integer.MAX_VALUE:hs - heaters[rh-1], rh==heaters.length? Integer.MAX_VALUE:heaters[rh]-hs);
                radius = Math.max(radius, r);
            }
            return radius;
        }
    

Log in to reply
 

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