Problem statement

https://leetcode.com/problems/minimize-max-distance-to-gas-station/

Solution

All we need to do is to use binary search given mid value we want to answer the question is number of stations we need to add is more than K. How many stations we need to add for each gap: it is ceil(d/mid) - 1, that is if say mid = 3, then for values d = 1, 2, 3 we do not need to add new stations, for d = 4, 5, 6 we need 1 station and so on.

Complexity

Time complexity is O(n log W), space complexity is O(n), where W is equal to possible biggest number in S (here 10^8) divided by accuracy we need to get answer (which is 10^{-6} here).

Solution

class Solution:
    def minmaxGasDist(self, S, k):
        diff = [j-i for i, j in zip(S, S[1:])]
        
        beg, end = 0, max(diff)
        while end - beg >= 1e-6:
            mid = (beg + end)/2
            if sum(ceil(d/mid)-1 for d in diff) > k:
                beg = mid
            else:
                end = mid

        return mid