Solution: Minimize Max Distance to Gas Station

Statement

You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.

A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within $10^{-6}$ of the actual answer.

Constraints:

• $10 \leq$ stations.length $\leq 2000$

• $0 \leq$ stations[i] $\leq 10^8$

• The stations array is sorted in a strictly increasing order.

• $1 \leq$ k $\leq 10^{6}$

Solution

To solve this problem, we aim to make the largest gap between any two adjacent stations as small as possible by placing the given k new stations. The first idea that might come to mind is: split the current largest gap evenly. For example, if stations = [0, 1, 2, 4] and k = 1, the gaps between the adjacent stations are [1, 1, 2]. One way to reduce the current maximum gap, 2, is to place the new station at position 3, making the new stations list [0, 1, 2, 3, 4]. Now, the gaps become [1, 1, 1, 1], and the maximum gap is reduced to 1, which is the correct answer. But for larger inputs with many unequal gaps and multiple new stations, it’s not obvious which gaps to break or how to distribute the new stations.

As we don’t know where exactly to place the k new stations, we flip the problem: instead of trying to find the positions, we'll try to find the smallest possible maximum gap (let’s call it $D$) that we can achieve by placing k stations. If we haven't added any new stations yet, the current maximum gap (let's call it $M$) gives us an upper bound, i.e., $D$ must lie somewhere between $0$ and $M$. We use this fact as our starting point, start finding $D$ with a range (from $0$ up to $M$), and keep narrowing it until we get the correct $D$.

We use binary search to optimally narrow down the value of $D$. The initial lower bound is $0$, and the upper bound is $M$. At each step, we calculate the middle value and use it as the potential value of $D$. Then, for this guessed value, we check if placing the k new stations is possible so that no gap is larger than $D$. We do this by going through each existing gap and figuring out how many new stations are needed to break that gap down to smaller parts, each no larger than $D$. We add this up across all gaps. If the total number of required stations is within k, then this guessed $D$ might be the answer, or maybe we can do even better, so we try smaller values. If it’s impossible, then the guess is too small, and we try bigger ones. We repeat this process until we get very close to the smallest possible answer. To be precise, we stop when the difference between our lower and upper bounds becomes less than $10^{-6}$, which gives us enough precision for the final answer.

Point to ponder: Why do we stop the binary search when the difference between the two ends becomes very small (right - left <= 10-6), instead of using the usual condition where the lower bound is less than the upper bound (left < right)?

In a standard binary search over a discrete sorted array, we stop when left > right (or when we find the exact item) because we’ve either found the target or exhausted all fixed positions.

However, in this gas station problem, we’re searching over a continuous range of real numbers (the possible maximum gaps), not discrete slots. There are infinitely many decimals between any two bounds, so pointers never “cross” in the usual sense. Instead, we maintain a numeric interval [left, right] and shrink it until the difference between right and left is below the required precision ($10^{-6}$). At that point, any number inside that tiny interval is effectively the same to six decimal places, so we stop.

Now, let’s look at the algorithm steps below:

• Initialize the search range as follows:

  • Set left (the lower bound) as 0, representing the smallest possible value for the maximum gap.

  • Set right (the upper bound) as the distance between the last and first stations, which is the maximum possible gap without any new stations.

  • Set epsilon = $10^{-6}$ for precision.

• Start the binary search, and while the difference between the upper and lower bounds is greater than the precision, i.e., right - left > epsilon, perform the following:  

  • Calculate the mid-point, mid, of the current range as the potential penalty value, i.e., the maximum possible gap, using the formula (left + right)/2.

  • Use the helper function, isPossible, to check if we can insert k or fewer stations such that no gap is greater than mid. The function iterates through pairs of adjacent gas stations and calculates how many new gas stations are required to reduce each gap to the penalty value or less. 

    • Try smaller distances by reducing the upper bound to the mid-point, right = mid if possible.

    • If not possible, try larger distances by increasing the lower bound to the mid-point, left = mid.

• After binary search ends, return left or right as the smallest possible maximum distance between two adjacent stations after placing k new stations.

Let’s look at the following illustration to get a better understanding of the solution: