Java O(nlogn) beats 93% with two pointers


  • 0
    L
    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int radius = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            int i = 0;
            int j = 0;
            while(i < houses.length){
                while (houses[i] >= heaters[j]) {
                    radius = houses[i] - heaters[j];
                    j++;
                    if (j == heaters.length) return Math.max(max, houses[houses.length - 1] - heaters[heaters.length -1]);
                }
                radius = Math.min(radius, heaters[j] - houses[i]);
                max = Math.max(max, radius);
                i ++;
                if (i != houses.length)radius += houses[i] - houses[i-1];
            }
            return max;
        }
    }
    

Log in to reply
 

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