C# - Binary Search heaters array, don't need to sort houses


  • 0

    sort the heaters to enable binary search for heaters array. Then just iterate through each house and find the nearest heater. Keep track to find the greatest distance from any house to it's nearest heater.

        public int FindRadius(int[] houses, int[] heaters) 
        {
            Array.Sort(heaters);
            int max = 0;
            for (int i = 0; i < houses.Length; i++)
            {
                int dist = ClosestDistanceBinarySearch(heaters, houses[i]);
                max = dist > max ? dist : max;
            }
            return max;
        }
        
        public int ClosestDistanceBinarySearch(int[] arr, int val)
        {
            int closestDist = Math.Abs(val - arr[0]);
            int left = 0;
            int right = arr.Length - 1;
            
            while (left <= right)
            {
                int mid = (left + right) / 2;
                
                if (val == arr[mid]) 
                {
                    closestDist = 0;
                    break;
                }
                else if (val < arr[mid])
                {
                    closestDist = arr[mid] - val < closestDist ? arr[mid] - val : closestDist;
                    right = mid - 1;
                }
                else
                {
                    closestDist = val - arr[mid] < closestDist ? val - arr[mid] : closestDist;
                    left = mid + 1;
                }
            }
            
            return closestDist;
        }
    

Log in to reply
 

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