Java binary search solution


  • 2
    M

    Idea: Search the left heater and right heater for each house. Then we can get the distance a house to its nearest heater. The maximum distance is the radius.

    Time Complexity: O(nlogn + mlogn),
    where m = houses.length, n = heaters.length.

        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(heaters); // nlogn
            final int N = heaters.length;
            int maxRadius = 0;
            for(int house : houses){ // m * logn
                int index = Arrays.binarySearch(heaters, house);
                if(index<0) index = -index-1;
                int dist_r = index<N ? heaters[index] - house : Integer.MAX_VALUE; // right heater
                int dist_l = index>0 ? house - heaters[index-1] : Integer.MAX_VALUE; // left heater
                maxRadius = Math.max(maxRadius, Math.min(dist_l, dist_r)); // max, min
            }
            return maxRadius;
        }
    

  • 0
    G

    @MadDetective Good Solution. I have a suggestion to make it more readable. Replacecurrent maxRadius with minRadius as variable name.


Log in to reply
 

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