Sharing an easy binary search solution


  • 0
    C

    The idea is easy to follow.

    public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(heaters);
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < houses.length; i++) {
                int j = Arrays.binarySearch(heaters, 0, heaters.length, houses[i]);
                if (j < 0) j = - (j + 1);
                if (j == 0) max = Math.max(max, heaters[j] - houses[i]);
                else if (j == heaters.length) max = Math.max(max, houses[i] - heaters[j-1]);
                else max = Math.max(max, Math.min(houses[i] - heaters[j - 1], heaters[j] - houses[i]));
            }
            return max;
        }
    

Log in to reply
 

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