Java Simple Solution using Binary Search


  • 0
    public int findRadius(int[] houses, int[] heaters) {
    	Arrays.sort(houses);
    	Arrays.sort(heaters);
    	int[] mins = new int[houses.length];
    	for(int i=0;i<houses.length;i++) {
    		mins[i] = binSearchClosest(houses[i],heaters,0,heaters.length);
    	}
    	int maxMin = 0;
    	for(int min: mins) {
    		maxMin = Math.max(maxMin, min);
    	}
    	return maxMin;
    }
    	
    public int binSearchClosest(int housePos, int[] heaters, int start, int end) {
    	
    	while(start<=end) {
    		int middle = (start+end)/2;
    		int currHeaterPos = heaters[middle];
    		if(housePos==currHeaterPos) return 0;
    		else if(currHeaterPos<housePos) {
    			if(middle+1>=heaters.length) return Math.abs(currHeaterPos-housePos);
    			int currHeaterPosPlusOne = heaters[middle+1];
    			if(currHeaterPosPlusOne>=housePos) {
    				return Math.min(Math.abs(currHeaterPos-housePos), Math.abs(currHeaterPosPlusOne-housePos));
    			} else {
    				start = middle+1;
    			}
    		} else { //currHeaterPos>housePos
    			if(middle-1<0) return Math.abs(currHeaterPos-housePos);
    			int currHeaterPosMinusOne = heaters[middle-1];
    			if(currHeaterPosMinusOne<=housePos) {
    				return Math.min(Math.abs(currHeaterPos-housePos), Math.abs(currHeaterPosMinusOne-housePos));
    			} else {
    				end=middle-1;
    			}
    		}
    	}
    	
    	return 0;
    }
    

Log in to reply
 

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