Short Python

  • 31

    Go through houses and heaters in ascending order. My i points to the current closest heater. Go to the next heater if the current house coordinate is larger than or equal to the middle between the current and the next heater.

    def findRadius(self, houses, heaters):
        heaters = sorted(heaters) + [float('inf')]
        i = r = 0
        for x in sorted(houses):
            while x >= sum(heaters[i:i+2]) / 2.:
                i += 1
            r = max(r, abs(heaters[i] - x))
        return r

    I btw started with
        while abs(heaters[i+1] - x) <= abs(heaters[i] - x):,
    the straight-forward check whether the next heater is closer than the current. Then I thought I probably don't need abs if I just use
        while heaters[i+1] - x <= x - heaters[i]:.
    That's obviously correct if x is between the heaters, because then that's the correct distances of x to the two heaters. Less obviously (but imho not surprisingly) it's also correct if x isn't between them. Finally, after rewriting it to
        while heaters[i] + heaters[i+1] <= 2 * x:
    I realized what that meant :-)

    Update: Another solution by using binary search, inspired by others:

    def findRadius(self, houses, heaters):
        return max(min(abs(house - heater)
                       for i in [bisect.bisect(heaters, house)]
                       for heater in heaters[i-(i>0):i+1])
                   for house in houses)

  • 2

    Your solution is brilliant as always! I think if given houses and heaters are sorted, your solution is O(n).

  • 0
    This post is deleted!

  • 3

    @StefanPochmann thx for showing us your thinking process Stefan! It is always rewarding to learn how people find the smart solution~

  • 0

    Hi, I was wondering why in this condition

        while abs(heaters[i+1] - x) <= abs(heaters[i] - x):

    it has to be <=. I think < also works, but actually < doesn't pass OJ. Could anyone help to clarify? Thanks.

  • 0

    @yizhu59 if "<", the heater index will stuck & won't advance if there are multiple heaters at one location.

  • 0

    @hlu07 Thanks a lot for your reply, it helps. I didn't think of this situation that there may have multiple heaters at the same location.

Log in to reply

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