LeetCode 774 - Minimize Max Distance to Gas Station

LeetCode Problem 774

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a sorted array called stations, where each value represents the position of an existing gas station on a one dimensional x-axis. We are also given an integer k, representing how many additional gas stations we are allowed to add.

After inserting exactly k new gas stations at arbitrary real-valued positions, we define the penalty as the maximum distance between any two adjacent gas stations. Our goal is to minimize this maximum distance.

In other words, we want to distribute the new gas stations in such a way that the largest gap between neighboring stations becomes as small as possible.

For example, suppose there is a gap of length 10 between two existing stations. If we place one new station inside that interval, the best possible arrangement splits the gap into two segments of length 5. If we place two new stations, we can split the interval into three equal parts of approximately 3.333.

The constraints are important:

• stations.length <= 2000
• k <= 10^6
• Station positions can be as large as 10^8

These limits tell us several things:

• A quadratic or cubic simulation approach will likely be too slow.
• Since k can be extremely large, we cannot explicitly simulate every possible placement naively.
• The answer is a floating point number, and the problem accepts answers within 10^-6, which strongly suggests binary search on the answer.

The input is guaranteed to be sorted in strictly increasing order, so we never need to sort the array ourselves.

Several edge cases are important:

• Very large gaps between stations, where many new stations may need to be inserted.
• Extremely large k, where the optimal maximum distance becomes very small.
• Intervals that divide unevenly, requiring careful rounding logic.
• Floating point precision issues during binary search termination.

Approaches

Brute Force Approach

A straightforward idea is to repeatedly place a new gas station into the currently largest interval.

For every insertion:

1. Find the interval with the maximum distance.
2. Insert a station in the middle of that interval.
3. Update the interval lengths.
4. Repeat k times.

This greedy approach can be implemented with a max heap. Each interval tracks how many pieces it has been divided into.

While this works reasonably well and often produces the optimal answer, its complexity becomes problematic when k is extremely large. Since k can reach 10^6, performing heap operations for every insertion becomes expensive.

The brute force simulation also focuses on constructing the arrangement directly, while the actual problem only asks for the minimum possible maximum distance. That observation leads to a much better strategy.

Key Insight

Instead of constructing the exact placement of stations, we can binary search the answer.

Suppose we guess a candidate maximum distance D.

The important question becomes:

Can we ensure every adjacent distance is at most D using at most k new stations?

For a gap of length gap:

• If gap <= D, no new station is needed.
• Otherwise, we must split the gap into smaller segments.

If we divide a gap into segments of maximum length D, the number of required additional stations is:

$$\left\lfloor \frac{gap}{D} \right\rfloor$$

More precisely:

$$\text{required} = \left\lceil \frac{gap}{D} \right\rceil - 1$$

This lets us efficiently check whether a candidate D is feasible.

Because feasibility is monotonic:

• If distance D is achievable, then any larger distance is also achievable.
• If distance D is not achievable, then any smaller distance is also impossible.

This monotonic property makes binary search applicable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k log n)	O(n)	Repeatedly split the largest interval using a heap
Optimal	O(n log W)	O(1)	Binary search on the answer, where W is the search range

Algorithm Walkthrough

1. Compute all adjacent gaps between consecutive gas stations.

For every pair stations[i] and stations[i+1], calculate:

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

The largest possible penalty cannot exceed the largest existing gap. 2. Initialize the binary search range.

The smallest possible penalty approaches 0, while the largest possible penalty is the maximum existing gap.

So we use:

• left = 0
• right = max_gap

3. Repeatedly binary search the answer.

At every iteration:

$$mid = \frac{left + right}{2}$$

Here, mid represents a candidate maximum allowed distance. 4. Check whether mid is feasible.

For every gap:

• Determine how many additional stations are needed so every segment becomes at most mid.

The required stations for a gap are:

$$\left\lfloor \frac{gap}{mid} \right\rfloor$$

with careful handling when the division is exact.

A simpler and safer implementation is:

$$\text{needed} += \text{int}(gap / mid)$$

and subtract one when perfectly divisible. 5. Compare the total required stations with k.

• If required stations <= k, then mid is achievable.

• Try to find an even smaller answer.

• Move right = mid.

• Otherwise:

• mid is too small.

• Move left = mid.

6. Continue until the search interval becomes sufficiently small.

Since answers within 10^-6 are accepted, we stop when:

$$right - left < 10^{-6}$$ 7. Return right or left.

Both values are effectively the same at termination.

Why it works

The algorithm relies on the monotonic nature of feasibility.

If a maximum distance D can be achieved using at most k stations, then any larger distance can also be achieved because relaxing the constraint never increases the number of required stations.

Binary search efficiently exploits this property to locate the smallest feasible distance. The feasibility check is correct because splitting each interval into equal-sized segments minimizes the maximum segment length for that interval.

Python Solution

from typing import List

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        def can_achieve(max_distance: float) -> bool:
            required_stations = 0

            for i in range(1, len(stations)):
                gap = stations[i] - stations[i - 1]

                additional = int(gap / max_distance)

                if gap % max_distance == 0:
                    additional -= 1

                required_stations += additional

                if required_stations > k:
                    return False

            return True

        left = 0.0
        right = 0.0

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

        precision = 1e-6

        while right - left > precision:
            mid = (left + right) / 2

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

        return right

The implementation begins by defining a helper function called can_achieve. This function determines whether a candidate maximum distance can be achieved using at most k additional stations.

For every adjacent pair of stations, we compute the gap length. We then calculate how many additional stations are needed to ensure no segment exceeds the candidate distance.

If the running total exceeds k, we immediately return False, which provides an important optimization.

The binary search range starts at 0.0 and extends to the largest existing gap. During each iteration, we test the midpoint:

• If feasible, we shrink the upper bound.
• Otherwise, we increase the lower bound.

The loop terminates once the interval becomes smaller than 10^-6, satisfying the required precision.

Go Solution

package main

func minmaxGasDist(stations []int, k int) float64 {
	canAchieve := func(maxDistance float64) bool {
		requiredStations := 0

		for i := 1; i < len(stations); i++ {
			gap := float64(stations[i] - stations[i-1])

			additional := int(gap / maxDistance)

			if gap == float64(additional)*maxDistance {
				additional--
			}

			requiredStations += additional

			if requiredStations > k {
				return false
			}
		}

		return true
	}

	left := 0.0
	right := 0.0

	for i := 1; i < len(stations); i++ {
		gap := float64(stations[i] - stations[i-1])

		if gap > right {
			right = gap
		}
	}

	precision := 1e-6

	for right-left > precision {
		mid := (left + right) / 2.0

		if canAchieve(mid) {
			right = mid
		} else {
			left = mid
		}
	}

	return right
}

The Go implementation follows the same logic as the Python version. Since Go distinguishes between integers and floating point values strictly, explicit float64 conversions are required during arithmetic.

The closure canAchieve captures stations and k directly, avoiding the need for extra parameters.

Unlike Python, Go does not have built-in arbitrary precision floating point handling, so we rely on float64, which is sufficient for the required precision.

Worked Examples

Example 1

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

Initial gaps:

Interval	Gap
1 -> 2	1
2 -> 3	1
3 -> 4	1
4 -> 5	1
5 -> 6	1
6 -> 7	1
7 -> 8	1
8 -> 9	1
9 -> 10	1

Maximum gap is 1.

Binary search begins:

left	right	mid
0	1	0.5

Now test 0.5.

Each gap of length 1 requires:

$$\frac{1}{0.5} - 1 = 1$$

So every interval needs one additional station.

Total required:

Gap	Stations Needed
1	1
1	1
1	1
1	1
1	1
1	1
1	1
1	1
1	1

Total = 9

Since 9 <= k, distance 0.5 is feasible.

Eventually the binary search converges to:

0.50000

Example 2

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

Compute gaps:

Interval	Gap
23 -> 24	1
24 -> 36	12
36 -> 39	3
39 -> 46	7
46 -> 56	10
56 -> 57	1
57 -> 65	8
65 -> 84	19
84 -> 98	14

Largest gap is 19.

Suppose binary search tests 14.

For every gap:

Gap	Needed Stations
1	0
12	0
3	0
7	0
10	0
1	0
8	0
19	1
14	0

Total required = 1

Since we can use exactly one new station, 14 is feasible.

Trying anything smaller than 14 would require more than one insertion.

Final answer:

14.00000

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log W)	Binary search performs logarithmic iterations over the answer range
Space	O(1)	Only constant extra variables are used

Here, n is the number of stations and W represents the numeric search range between 0 and the maximum existing gap.

The binary search typically performs around 50 to 60 iterations to achieve 10^-6 precision. During each iteration, we scan all station gaps once.

Test Cases

from typing import List

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        def can_achieve(max_distance: float) -> bool:
            required_stations = 0

            for i in range(1, len(stations)):
                gap = stations[i] - stations[i - 1]

                additional = int(gap / max_distance)

                if gap % max_distance == 0:
                    additional -= 1

                required_stations += additional

            return required_stations <= k

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

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

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

        return right

solution = Solution()

# Provided example 1
assert abs(solution.minmaxGasDist(
    [1,2,3,4,5,6,7,8,9,10], 9
) - 0.5) < 1e-5

# Provided example 2
assert abs(solution.minmaxGasDist(
    [23,24,36,39,46,56,57,65,84,98], 1
) - 14.0) < 1e-5

# Single large gap
assert abs(solution.minmaxGasDist(
    [1, 11], 1
) - 5.0) < 1e-5

# Multiple insertions in same interval
assert abs(solution.minmaxGasDist(
    [1, 11], 2
) - (10 / 3)) < 1e-5

# Uneven division
assert abs(solution.minmaxGasDist(
    [0, 9], 2
) - 3.0) < 1e-5

# Large k
assert solution.minmaxGasDist(
    [0, 100], 99
) < 1.01

# Already evenly spaced
assert abs(solution.minmaxGasDist(
    [0, 5, 10, 15], 3
) - 2.5) < 1e-5

# Large coordinates
assert abs(solution.minmaxGasDist(
    [0, 100000000], 1
) - 50000000.0) < 1e-5

Test	Why
[1,2,3,4,5,6,7,8,9,10], k=9	Validates evenly distributed insertions
[23,24,36,...], k=1	Validates handling of irregular gaps
[1,11], k=1	Tests simple midpoint insertion
[1,11], k=2	Tests multiple insertions in one interval
[0,9], k=2	Tests exact equal partitioning
[0,100], k=99	Tests very large k
[0,5,10,15], k=3	Tests balanced existing intervals
[0,100000000], k=1	Tests very large coordinate values

Edge Cases

One important edge case occurs when a gap divides perfectly by the candidate maximum distance. For example, if a gap is 10 and the candidate distance is 5, we only need one extra station, not two. A careless implementation using plain integer division may overcount required stations. The implementation handles this by subtracting one when the division is exact.

Another important edge case is extremely large values of k. When many stations can be inserted, the optimal answer becomes very small. This can expose floating point precision problems or cause infinite binary search loops if the stopping condition is incorrect. The implementation uses a precision threshold of 10^-6, matching the problem requirements.

A third edge case involves very large station coordinates, up to 10^8. Integer arithmetic itself remains safe, but calculations involving floating point division must be handled carefully. Both implementations use floating point arithmetic consistently during binary search and feasibility checks, preventing overflow or truncation issues.