LeetCode 774: Minimize Max Distance to Gas Station

Problem Restatement

We are given a sorted array stations.

Each value in stations is the position of an existing gas station on the x-axis.

We are also given an integer k.

We must add exactly k new gas stations. A new gas station can be placed anywhere on the x-axis, including non-integer positions.

After adding the new stations, define the penalty as the maximum distance between two adjacent gas stations.

Return the smallest possible penalty. Answers within 10^-6 of the actual answer are accepted.

Input and Output

Example function shape:

def minmaxGasDist(stations: list[int], k: int) -> float:
    ...

Examples

Example 1:

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

Output:

0.5

There are 9 gaps of length 1.

If we add one station in the middle of each gap, every gap becomes length 0.5.

So the minimized maximum distance is 0.5.

Example 2:

stations = [23, 24, 36, 39, 46, 56, 57, 65, 84, 98]
k = 1

Output:

14.0

With one new station, the best placement reduces the largest possible adjacent gap to 14.

First Thought: Place Stations in the Largest Gap

A natural idea is to repeatedly place a new station in the currently largest gap.

This can work if implemented carefully with a heap.

But there is an easier and more robust approach.

Instead of deciding exactly where to place stations first, we ask a yes-or-no question:

Can we make every adjacent distance at most x using at most k new stations?

If yes, maybe we can make x smaller.

If no, x is too small.

This is binary search on the answer.

Key Insight

The answer is a real number.

For a candidate maximum distance x, we can count how many new stations are needed.

Suppose there is a gap of length d.

We want to split it into smaller pieces, each of length at most x.

If we add m stations inside this gap, the gap becomes m + 1 segments.

We need:

d / (m + 1) <= x

So:

m + 1 >= d / x

The number of stations needed for this gap is:

ceil(d / x) - 1

In code, we can compute this carefully as:

int((d - 1e-12) / x)

The tiny subtraction avoids overcounting when d is exactly divisible by x.

For example, if d = 4 and x = 2, we need only one new station:

0 ---- 2 ---- 4

The formula gives:

ceil(4 / 2) - 1 = 2 - 1 = 1

Feasibility Check

Define:

can(max_dist)

This returns True if we can make all gaps at most max_dist using at most k stations.

For each adjacent pair:

gap = stations[i + 1] - stations[i]

add the number of stations needed for this gap.

If the total needed is less than or equal to k, then max_dist is feasible.

Why at most k instead of exactly k?

Because if a distance is feasible using fewer than k stations, we can always place the remaining stations somewhere without increasing the maximum adjacent distance.

Binary Search

The answer lies between:

0

and the largest existing gap.

Let:

left = 0.0
right = max_gap

Then repeat:

1. Let mid = (left + right) / 2.
2. If mid is feasible, move right = mid.
3. Otherwise, move left = mid.

After enough iterations, right is very close to the smallest feasible distance.

Algorithm

1. Compute the largest existing gap.
2. Binary search between 0.0 and that gap.
3. For each midpoint:
   1. Count how many stations are needed to make every gap at most mid.
   2. If the count is at most k, the midpoint is feasible.
   3. Otherwise, it is too small.
4. Return the right boundary after convergence.

Correctness

For any candidate distance x, the feasibility check computes the minimum number of new stations needed so that every original gap is split into segments of length at most x.

If the required number is at most k, then a placement exists whose penalty is at most x.

If the required number is greater than k, then no placement using only k stations can make every adjacent distance at most x.

This feasibility property is monotonic. If a distance x is feasible, then any larger distance is also feasible. If x is not feasible, then any smaller distance is also not feasible.

Binary search on this monotonic predicate finds the smallest feasible distance to the required precision.

Therefore, the returned value is the minimum possible penalty.

Complexity

Let n = len(stations).

Let E be the precision target, such as 1e-6.

Implementation

class Solution:
    def minmaxGasDist(self, stations: list[int], k: int) -> float:
        def can(max_dist: float) -> bool:
            needed = 0

            for i in range(len(stations) - 1):
                gap = stations[i + 1] - stations[i]
                needed += int((gap - 1e-12) / max_dist)

                if needed > k:
                    return False

            return needed <= k

        left = 0.0
        right = 0.0

        for i in range(len(stations) - 1):
            right = max(right, stations[i + 1] - stations[i])

        while right - left > 1e-6:
            mid = (left + right) / 2

            if can(mid):
                right = mid
            else:
                left = mid

        return right

Code Explanation

The helper function checks whether a candidate distance is possible:

def can(max_dist: float) -> bool:

For every gap, it counts how many stations are needed:

needed += int((gap - 1e-12) / max_dist)

If the count already exceeds k, we can stop early:

if needed > k:
    return False

The binary search range starts at 0 and the largest current gap:

left = 0.0
right = max_gap

At each step:

mid = (left + right) / 2

If mid is feasible, we try a smaller value:

right = mid

Otherwise, we need a larger allowed distance:

left = mid

When the interval is smaller than 1e-6, returning right gives an accepted answer.

Testing

def close(a: float, b: float) -> bool:
    return abs(a - b) <= 1e-6

def run_tests():
    s = Solution()

    assert close(
        s.minmaxGasDist([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9),
        0.5,
    )

    assert close(
        s.minmaxGasDist([23, 24, 36, 39, 46, 56, 57, 65, 84, 98], 1),
        14.0,
    )

    assert close(
        s.minmaxGasDist([1, 5], 1),
        2.0,
    )

    assert close(
        s.minmaxGasDist([1, 5], 3),
        1.0,
    )

    assert close(
        s.minmaxGasDist([0, 10], 4),
        2.0,
    )

    print("all tests passed")

run_tests()

Test meaning: