Binary search solution


  • 0
    1. Sort the houses and heaters.
    2. For each house 'h', find a heater that is to its west (ie, less than or equal to house's position). Compare the distance between the house and the west heater and the house and east heater(westheater + 1). Choose the smaller distance.
    3. Maximum of the distance chosen for all the houses is the answer.

    Special cases

    1. The house does not have any heater to the west (ie house's position is less than heaters[0]). The only heater that can cover the house is the first heater and the distance is heaters[0]-h
    2. The house does not have any heater to the east (ie house's position is greater than or equal to last heater). The only heater that can cover this house is the last heater and the distance is h-heaters[heaters.Length-1]
    public class Solution 
    {
       public int FindRadius(int[] houses, int[] heaters)
        {
            int maxRadius = 0;
            Array.Sort(houses);
            Array.Sort(heaters);
    
            foreach (var h in houses)
            {
                int westHeater = GetClosestWestHeater(h, heaters, 0, heaters.Length - 1);
                int curRadius;
                if (westHeater == -1)
                {
                    curRadius = heaters[0] - h;
                }
                else if (westHeater == heaters.Length-1)
                {
                    curRadius = h- heaters[westHeater];
                }
                else
                {
                    // Find the distance that is shortest between the closest and next highest
                    int eastHeater = westHeater + 1;
                    curRadius = Math.Min(h - heaters[westHeater], heaters[eastHeater] - h);
                }
    
                maxRadius = Math.Max(curRadius, maxRadius);
            }
    
            return maxRadius;
        }
        private int GetClosestWestHeater(int house, int[] heaters, int start, int end)
        {
            while (start + 1 < end)
            {
                int mid = start + (end - start) / 2;
                if (house <= heaters[mid])
                {
                    end = mid;
                }
                else
                {
                    start = mid + 1;
                }
            }
    
            // We ll have two elements in start and end.
            if (heaters[start] > house)
            {
                return start - 1;
            }
            else if (house >= heaters[end])
            {
                return end;
            }
            else
            {
                return start;
            }
        }
    }
    

Log in to reply
 

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