Java Solution O (m+n) - find the distance to the nearest heater


  • 0
    G
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
     
        int res = 0;
        int ht  = 0;
        int nh  = heaters.length; 
        for (int i = 0; i < houses.length; i ++) {
            int d = Math.abs(heaters[ht] - houses[i]);
            while (ht + 1 < nh && Math.abs(heaters[ht+1] - houses[i]) <= d) {
                ht ++;
                d = Math.abs(heaters[ht] - houses[i]);
            }
                
            res = Math.max(res, d);
        }
            
        return res;
     }
    

  • 0
    D

    This solution is O(nlogn) because the sorts take O(nlogn) time.


Log in to reply
 

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