Short and simple solution in Java


  • 0
    T

    Sort the location and then find the nearest heater for each house one by one. Sorting is O(NlogN), the following is O(N);

    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int nheaters=heaters.length;
        int heaterloc=0;
        int res=0;
        for(int houseloc:houses){
            while(heaterloc+1<nheaters && houseloc-heaters[heaterloc] > heaters[heaterloc+1]-houseloc){
                heaterloc++;
            }
            res=Math.max(Math.abs(houseloc-heaters[heaterloc]),res);
        }
        return res;
    }

Log in to reply
 

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