Readable O(n*log(m)) solution in Python

  • 0
    class Solution(object):
        def findRadius(self, houses, heaters):
            :type houses: List[int]
            :type heaters: List[int]
            :rtype: int
            def findRadiusHelper(house, sortedHeaters):
                start,end = 0,len(sortedHeaters)-1
                r = sys.maxint
                while start <= end:
                    mid = (start+end) // 2
                    r = min(r, abs(house - sortedHeaters[mid]))
                    if sortedHeaters[mid] < house:
                        start = mid + 1
                        end = mid - 1
                return r
            ret = 0
            for house in houses:
                ret = max(ret, findRadiusHelper(house, heaters))
            return ret

    Basic binary search based approach. For each house, we find the corresponding radius among all heaters. We return the maximum radius found. The heater positions are sorted to speed up the process.

Log in to reply

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