HardBinary SearchArrayGreedy

Minimize Max Distance to Gas Station

1 approach, code in every language

Gas stations sit along a straight highway at strictly increasing positions given in an array. You may add k brand-new stations anywhere on the highway, including at fractional positions between existing ones. After placing them, the penalty is the largest distance between two neighboring stations.

Distribute the k new stations to make that largest neighboring gap as small as possible, and return the resulting minimum possible maximum distance. Because positions are real numbers, the answer is a decimal value that you approximate to within a small tolerance.

Example 1

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9

Output: 0.50000

There are nine unit gaps and nine stations to place. Dropping one station in the middle of each gap halves every gap to 0.5, which becomes the largest distance.

Example 2

Input: stations = [1,2,3,10], k = 2

Output: 2.33333

The dominant gap is the stretch of length 7 between 3 and 10. Placing both new stations inside it splits that stretch into three equal parts of 7/3, which outweighs the two unit gaps.

Constraints

2 <= stations.length <= 10^4
0 <= stations[i] <= 10^8
stations is sorted in strictly increasing order
1 <= k <= 10^6

Binary Search on the Distance

Binary search over the real-valued maximum distance; for a candidate distance, count how many stations are required and compare against k.

Loading animation…

Intuition

Suppose we fix a target maximum distance d. A gap of length g can be forced below d by inserting floor(g / d) extra stations inside it. Summing that count across all gaps tells us how many stations a target d demands. This required count only rises as d shrinks, giving a monotonic relationship perfect for binary search. We search for the smallest d whose required station count still fits within our budget of k, converging by shrinking a floating-point window until it is tighter than a small tolerance.

Algorithm walkthrough

1Set lo = 0 and hi = the largest existing gap, which is the widest the answer could ever be.
2Take mid as the midpoint distance and, for each adjacent gap, add floor(gap / mid) to a running station count.
3If the required stations are at most k, this distance is achievable, so tighten hi down to mid.
4If the required stations exceed k, mid is too small to afford, so raise lo up to mid.
5Repeat until hi - lo drops below the tolerance, then return hi as the minimized maximum distance.

Implementation

from typing import List

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        def needed(d: float) -> int:
            count = 0
            for i in range(1, len(stations)):
                count += int((stations[i] - stations[i - 1]) / d)
            return count
        lo, hi = 0.0, float(stations[-1] - stations[0])
        while hi - lo > 1e-6:
            mid = (lo + hi) / 2
            if needed(mid) <= k:
                hi = mid
            else:
                lo = mid
        return hi

Time

O(n log(R / eps)), where n is the number of stations, R is the widest gap, and eps is the tolerance

Space

O(1)

Each iteration scans the gaps once; the iteration count depends on how finely the distance window is narrowed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free