Concise solution using NavigableSet(no sorting, less than 10 lines)

  • 0

    Leverage NavigableSet and its ceiling/floor methods to find lowerbound and upperbound of each house, keep tracking the max of min difference while iterating the houses.

    P.S Remember to import the java.util.NavigableSet and java.util.TreeSet.

    public int findRadius(int[] houses, int[] heaters) {
        int radius = 0;
        NavigableSet<Integer> set = new TreeSet<>();
        for(int heater : heaters) set.add(heater);
        for(int house : houses) {
            int low = set.floor(house) == null ? Integer.MAX_VALUE : set.floor(house);
            int high = set.ceiling(house) == null ? Integer.MAX_VALUE : set.ceiling(house);
            int cur = Math.min(Math.abs(house - low), Math.abs(house - high));
            radius = Math.max(cur, radius);
        return radius;

Log in to reply

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