Java max_i(min(pos-leftneighbor, rightneighbor-pos)) solution


  • 0
    D
    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            if (houses == null || houses.length == 0) {
                return 0;
            }
            if (heaters == null || heaters.length == 0) {
                return 0;
            }
            Arrays.sort(houses);
            Arrays.sort(heaters);
            Integer[] leftneighbor = new Integer[houses.length];
            for (int houseInd = 0, heatInd = 0; houseInd < houses.length;) {
                if (houses[houseInd] < heaters[heatInd]) {
                    houseInd++;
                } else if (heatInd == heaters.length - 1 || houses[houseInd] < heaters[heatInd + 1]) {
                    leftneighbor[houseInd] = heaters[heatInd];
                    houseInd++;
                } else {
                    heatInd++;
                }
            }
            Integer[] rightneighbor = new Integer[houses.length];
            for (int houseInd = houses.length - 1, heatInd = heaters.length - 1; houseInd >= 0;) {
                if (houses[houseInd] > heaters[heatInd]) {
                    houseInd--;
                } else if (heatInd == 0 || houses[houseInd] > heaters[heatInd - 1]) {
                    rightneighbor[houseInd] = heaters[heatInd];
                    houseInd--;
                } else {
                    heatInd--;
                }
            }
            int minRadius = Integer.MIN_VALUE;
            for (int i = 0; i < houses.length; i++) {
                minRadius = Math.max(minRadius, Math.min(leftneighbor[i] == null ? Integer.MAX_VALUE : houses[i] - 
                        leftneighbor[i], rightneighbor[i] == null ? Integer.MAX_VALUE : rightneighbor[i] - houses[i]));
            }
            return minRadius;
        }
    }
    

Log in to reply
 

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