O(m+n) linear solution, one pass


  • 0
    F

    Each house should be heated by the heater closest to it.

    '''
    public class Solution {
    public int FindRadius(int[] houses, int[] heaters) {
    Array.Sort(houses);
    Array.Sort(heaters);
    var min_radius = 0;
    var n = heaters.Length;
    var m = houses.Length;
    var j = 0;

        for(var i = 0; i < n; i++){
            while(j < m && (i == n-1 || Math.Abs(houses[j] - heaters[i]) < Math.Abs(houses[j]-heaters[i+1]))){
                min_radius = Math.Max(Math.Abs(houses[j]-heaters[i]), min_radius);
                j++;
            }
        }
        return min_radius;
    }
    

    }
    ''''


  • 0
    F

    Forget about the sorting complexity = = = = =


Log in to reply
 

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