Problem statement

https://leetcode.com/problems/heaters/

Solution

Go through houses and heaters in ascending order. Variable i points to the last house before the heater. We choose minimum between heater and two closest houses, and then find maximum over all these minimums.

Complexity

Complexity is O(n log n + m log m), where n is number of houses and m is number of heaters.

Code

class Solution(object):
    def findRadius(self, houses, heaters):
        heaters = [float('-inf')] + sorted(heaters) + [float('inf')]
        ans, i = 0, 0
        for house in sorted(houses):
            while house > heaters[i+1]: 
                i += 1
            dis = min(house - heaters[i], heaters[i+1]- house)
            ans = max(ans, dis)
        return ans

Remark

We can also sort heaters and use binary search for each house to find between which two houses it is, and choose the smallest of this values. Then we choose maximum over all these minimums. Complexity is O(n log n + nlog m).