☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Minimize Max Distance to Gas Station

Hard TUF ID 78 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Gas stations sit on a straight highway at the sorted, distinct positions stations[0] < stations[1] < ... < stations[n-1]. You may build k new stations anywhere on the line, including at non-integer positions. After building, look at the largest distance between two neighbouring stations; call it the penalty. Place the k new stations so that the penalty is as small as possible, and return that minimum penalty. Answers within 10^-6 of the true value are accepted.

Constraints: 1 ≤ n ≤ 2000, 0 ≤ stations[i] ≤ 10^8, 0 ≤ k ≤ 10^6.

Example 1

stations = [1, 2, 3, 4, 5], k = 4
answer = 0.5         // one new station in the middle of each of the four gaps

Example 2

stations = [1, 13, 17, 23], k = 5
answer = 3.0         // gaps 12, 4, 6 get 3, 1, 1 new stations: sections of 3, 2, 3

Example 3

stations = [1, 2, 3, 4, 5], k = 0
answer = 1.0         // nothing to build; the largest existing gap stays

Two observations drive everything below. First, a new station only matters inside the gap it lands in, so the problem is really about deciding how many new stations each gap receives. Second, inside one gap it is always best to spread its new stations evenly: a gap of length g that receives c stations is cut into c + 1 sections, the longest of which is at least g / (c + 1), and equal spacing achieves exactly that.

Approach 1: Brute force, greedy placement one station at a time

Intuition. Place the k stations one by one. Each time, look at every gap, compute the length of its sections given how many stations it already holds, and drop the next station into the gap whose sections are currently the longest. The penalty is the longest section anywhere, so the only way to reduce it is to shrink the current worst gap; putting a station anywhere else leaves the penalty unchanged. Repeating the locally forced move k times yields the optimum.

Algorithm.

  1. If there are fewer than two stations, there is no gap: return 0.
  2. Keep placed[i], the number of new stations already in gap i (between stations[i] and stations[i+1]).
  3. Repeat k times: find the gap maximising (stations[i+1] − stations[i]) / (placed[i] + 1) and increment its placed[i].
  4. Return the maximum section length over all gaps.
static double bruteForce(int[] stations, int k) {
    int n = stations.length;
    if (n < 2) return 0;
    int[] placed = new int[n - 1];                   // new stations already dropped into gap i
    for (int t = 0; t < k; t++) {
        int best = 0;
        double bestLen = -1;
        for (int i = 0; i < n - 1; i++) {
            double len = (double) (stations[i + 1] - stations[i]) / (placed[i] + 1);
            if (len > bestLen) { bestLen = len; best = i; }
        }
        placed[best]++;
    }
    double ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans = Math.max(ans, (double) (stations[i + 1] - stations[i]) / (placed[i] + 1));
    }
    return ans;
}

Complexity. Time O(k × n): each of the k placements scans all n − 1 gaps. Space O(n) for the counters.

With k up to 10^6 and n up to 2000 that is around 2 × 10^9 operations, too slow. The scan for the worst gap is the bottleneck.

Approach 2: Better, the same greedy with a max-heap

Intuition. The brute force spends O(n) per step just to find the gap with the longest sections. A priority queue keyed on section length hands over that gap in O(log n). Pop the worst gap, give it one more station, push it back with its new, shorter section length.

Algorithm.

  1. If n < 2, return 0.
  2. Push every gap into a max-heap as {sectionLength, gapIndex}; initially the section length is the full gap.
  3. Repeat k times: pop the top, increment placed[gap], push {gap / (placed[gap] + 1), gap}.
  4. The top of the heap is now the longest section: return it.
static double better(int[] stations, int k) {
    int n = stations.length;
    if (n < 2) return 0;
    int[] placed = new int[n - 1];
    PriorityQueue<double[]> heap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));   // {sectionLength, gapIndex}
    for (int i = 0; i < n - 1; i++) heap.offer(new double[]{stations[i + 1] - stations[i], i});
    for (int t = 0; t < k; t++) {
        int gap = (int) heap.poll()[1];
        placed[gap]++;
        heap.offer(new double[]{(double) (stations[gap + 1] - stations[gap]) / (placed[gap] + 1), gap});
    }
    return heap.peek()[0];
}

Complexity. Time O((n + k) log n): building the heap and k pop/push rounds. Space O(n).

This is a real improvement, but the work still grows with k. Building a million stations one at a time is wasteful when we could ask a different question entirely.

Approach 3: Optimal, binary search on the answer

Intuition. Flip the question around. Instead of “where do the stations go?”, ask “can we make every section at most d long with at most k new stations?” For a single gap of length g, the fewest stations that achieve sections of length at most d is ceil(g / d) − 1: the gap must be cut into at least ceil(g / d) sections, and s sections need s − 1 cuts. Summing over all gaps gives the minimum number of stations needed for the penalty d; compare it to k.

That predicate is monotone in d: a larger allowed distance never needs more stations. The answer is the smallest d for which the predicate holds, which binary search finds. Because d is a real number, we do not stop when lo > hi; we halve the interval a fixed number of times, which shrinks it far below the required precision.

Algorithm.

  1. If n < 2, return 0.
  2. Set lo = 0 and hi to the largest existing gap (placing nothing already achieves that penalty).
  3. Repeat 100 times: mid = (lo + hi) / 2. If feasible(mid), set hi = mid; otherwise set lo = mid.
  4. Return hi, which is always a feasible value.
static boolean feasible(int[] stations, int k, double d) {
    long needed = 0;
    for (int i = 0; i < stations.length - 1; i++) {
        int gap = stations[i + 1] - stations[i];
        long inside = (long) Math.ceil(gap / d) - 1;   // ceil(gap / d) sections need one fewer new stations
        if (inside > k - needed) return false;
        needed += inside;
    }
    return true;
}

static double optimal(int[] stations, int k) {
    int n = stations.length;
    if (n < 2) return 0;
    double lo = 0, hi = 0;
    for (int i = 0; i < n - 1; i++) hi = Math.max(hi, stations[i + 1] - stations[i]);
    for (int iter = 0; iter < 100; iter++) {         // 100 halvings shrink any gap far below 1e-6
        double mid = (lo + hi) / 2;
        if (feasible(stations, k, mid)) hi = mid; else lo = mid;
    }
    return hi;
}

Dry run of the feasibility check on stations = [1, 13, 17, 23], k = 5. The gaps are 12, 4, 6.

d stations for gap 12 for gap 4 for gap 6 total ≤ 5?
6.0 ceil(2) − 1 = 1 ceil(0.67) − 1 = 0 ceil(1) − 1 = 0 1 yes
3.0 ceil(4) − 1 = 3 ceil(1.33) − 1 = 1 ceil(2) − 1 = 1 5 yes
2.9 ceil(4.14) − 1 = 4 ceil(1.38) − 1 = 1 ceil(2.07) − 1 = 2 7 no

Every d at or above 3 is feasible and every d below 3 is not, so the halving converges to 3.0.

Complexity. Time O(n × I) where I = 100 is the number of halvings, independent of k. Space O(1).

Why 100 iterations? Each halving cuts the interval in two, so after 100 steps an initial width of 10^8 has shrunk by a factor of 2^100, far beyond the 10^-6 tolerance and beyond what a double can even represent. An alternative stopping rule is while (hi − lo > 1e-6); the fixed count is simpler to reason about and immune to floating-point stalls.

Edge cases and pitfalls