Binary Search: Closest heater to each house
- Given a house i, say j is the location of the closest heater to it. Say distI(i) = abs(i-j) is the minimum distance between the house i and a heater. The solution of our problem is to find max(dist(0), dist(1), dist(2), ...dist(n-1)).
- We can sort the input heaters. Then for every house i, we find the leftmost index idx in the sorted heater list to insert the position of this house using binary search.
- idx can be 0, len(heaters), or lie between 0 and len(heaters). We can use this to find dist(i).
bisect module in Python
- Key idea is to use bisect_left in the bisect module. bisect_left returns the leftmost index in sorted list to insert a given element
- Think of the leftmost index where you will add the new element and push all the remaining on the right by 1 so that the new array still remains sorted. This visualization immediately tells us why bisect_left([1,2,3], 4) will be 3 or bisect_left([1,2,3], 2.5) will 2.
from bisect import bisect_left class Solution(object): def findRadius(self, houses, heaters): """ :type houses: List[int] :type heaters: List[int] :rtype: int """ heaters.sort() max_so_far = float('-inf') for x in houses: idx = bisect_left(heaters, x) if 0<idx<len(heaters): dist = min(x-heaters[idx-1], heaters[idx]-x) else: dist = heaters-x if idx == 0 else x - heaters[-1] max_so_far = max(dist, max_so_far) return max_so_far