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


  • 0
    P
    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
                    else:
                        end = mid - 1
                return r
           
            ret = 0
            heaters.sort()
            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.