# 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

| Item | Meaning |
|---|---|
| Input | `stations`, sorted existing station positions |
| Input | `k`, number of new stations to add |
| Output | Minimum possible maximum adjacent distance |
| Placement | New stations may be placed at real-number positions |
| Precision | Answer is accepted within `10^-6` |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
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:

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

Output:

```python
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:

```text
d / (m + 1) <= x
```

So:

```text
m + 1 >= d / x
```

The number of stations needed for this gap is:

```python
ceil(d / x) - 1
```

In code, we can compute this carefully as:

```python
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:

```text
0 ---- 2 ---- 4
```

The formula gives:

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

## Feasibility Check

Define:

```python
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:

```python
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:

```text
0
```

and the largest existing gap.

Let:

```python
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`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * log(max_gap / E))` | Each feasibility check scans all gaps |
| Space | `O(1)` | Only counters and bounds are stored |

## Implementation

```python
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:

```python
def can(max_dist: float) -> bool:
```

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

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

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

```python
if needed > k:
    return False
```

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

```python
left = 0.0
right = max_gap
```

At each step:

```python
mid = (left + right) / 2
```

If `mid` is feasible, we try a smaller value:

```python
right = mid
```

Otherwise, we need a larger allowed distance:

```python
left = mid
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| Consecutive stations with `k = 9` | Main example, every unit gap is split |
| Large varied gaps with `k = 1` | Confirms binary search over uneven gaps |
| One gap, one station | Splits distance into two equal parts |
| One gap, three stations | Splits distance into four equal parts |
| Gap `10`, four stations | Produces five segments of length `2` |