JS binary search solution, simple idea


  • 0
    H

    The idea is simple, sort the heaters first. Then for each house position, search the closest heater. The distance between the house and its closest heater is the radius required to heat the house. Then we just find the max of those closest distance.

    var findRadius = function(houses, heaters) {
    
        //first sorted the heaters for binary search
        heaters.sort(function(a, b) {return a - b;});
        
       //find the maximum value of the closest distances
        return houses.reduce(function(maxDis, house) {
            return Math.max(maxDis, findClosestDis(heaters, house))
        }, -Number.MAX_VALUE);
    };
    
    // heaters already sorted
    function findClosestDis(heaters, house) {
        var start = 0, end = heaters.length - 1;
        while (start <= end) {
            var mid = Math.floor((start + end) / 2);
            var _pos = heaters[mid];
            
            if (_pos === house) {
                return 0;
            } else if (_pos > house) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        //ending condition is start = end + 1
        var leftDis = end >= 0 ? house - heaters[end] : Number.MAX_VALUE;
        var rightDis = start < heaters.length ? heaters[start] - house: Number.MAX_VALUE;
        var min = Math.min(leftDis, rightDis);
        return min;
    };
    
    
    

Log in to reply
 

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