Minimize Max Distance to Gas Station

Hard Binary Search Binary Search on Answer Space Original on LeetCode

Reported atAmazon

Minimize Max Distance to Gas Station is a hard binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the answer), runs in O(n log(W / ε)) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (greedy, linear scan per station) up.

Problem

Gas stations stand on a straight road at the coordinates in the sorted array stations. You may build exactly k new stations, at any real-valued coordinates (not necessarily integers).

After building, look at the distance between every pair of neighbouring stations and take the largest one. Place the new stations so that this largest distance is as small as possible, and return it.

Examples

Example 1

Input
stations = [0, 4, 10], k = 2
Output
3.00000
Why
Put one new station at 7 (splitting the gap of 6 into 3 + 3) and one at 2 (splitting the gap of 4 into 2 + 2). The largest gap is now 3.

Example 2

Input
stations = [3, 8, 9, 20], k = 1
Output
5.50000
Why
The only useful move is to halve the widest gap, 11, at 14.5. The largest gap becomes 5.5.

Example 3

Input
stations = [1, 2, 3, 4], k = 3
Output
0.50000
Why
Each of the three unit gaps gets one station in its middle.

Constraints

  • 2 <= stations.length <= 2000
  • 0 <= stations[i] <= 10^8
  • stations is strictly increasing.
  • 1 <= k <= 10^6
  • Answers within 10^-6 of the true value are accepted.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (greedy, linear scan per station)O(k·n)O(n)
Better (greedy with a max-heap)O(n + k log n)O(n)
Optimal (binary search on the answer)O(n log(W / ε))O(1)

1Brute force (greedy, linear scan per station)

TimeO(k·n)k placements, each scanning all n - 1 gaps.
SpaceO(n)One counter per gap.

Keep, for every gap, how many new stations it has received. Each new station goes into the gap whose current piece length gap / (count + 1) is the largest. Find that gap with a full scan every time.

  1. count[i] = 0 for every gap i between stations[i] and stations[i + 1].
  2. Repeat k times: scan all gaps, pick the one with the largest gap / (count + 1), and increase its count.
  3. Return the largest gap / (count + 1) over all gaps.
class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        int n = stations.length;
        int[] count = new int[n - 1];
        for (int s = 0; s < k; s++) {
            int best = 0;
            for (int i = 1; i < n - 1; i++) {
                double cur = (double) (stations[i + 1] - stations[i]) / (count[i] + 1);
                double top = (double) (stations[best + 1] - stations[best]) / (count[best] + 1);
                if (cur > top) {
                    best = i;
                }
            }
            count[best]++;
        }
        double ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ans = Math.max(ans, (double) (stations[i + 1] - stations[i]) / (count[i] + 1));
        }
        return ans;
    }
}

2Better (greedy with a max-heap)

TimeO(n + k log n)Each of the k placements is one pop and one push on a heap of n - 1 gaps.
SpaceO(n)The heap and the counters hold one entry per gap.

Same greedy rule, but keep the gaps in a max-heap ordered by their current piece length gap / (count + 1). The top of the heap is always the gap that should get the next station.

  1. Push every gap index into a max-heap keyed by gap / (count + 1), with count = 0.
  2. Repeat k times: pop the top gap, increase its count, push it back with the new key.
  3. The key on top of the heap is the answer.
class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        int n = stations.length;
        int[] count = new int[n - 1];
        double[] gap = new double[n - 1];
        for (int i = 0; i < n - 1; i++) {
            gap[i] = stations[i + 1] - stations[i];
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (a, b) -> Double.compare(gap[b] / (count[b] + 1), gap[a] / (count[a] + 1)));
        for (int i = 0; i < n - 1; i++) {
            pq.add(i);
        }
        for (int s = 0; s < k; s++) {
            int i = pq.poll();
            count[i]++;
            pq.add(i);
        }
        int top = pq.peek();
        return gap[top] / (count[top] + 1);
    }
}

3Optimal (binary search on the answer)

TimeO(n log(W / ε))About log2(10^8 / 10^-6) ≈ 47 rounds, each a single pass over the n - 1 gaps (W is the widest gap, ε = 10^-6).
SpaceO(1)Only the bounds and a running count.

Guess a maximum distance D. A gap of length g needs floor(g / D) new stations to bring every piece down to at most D. Add that up over all gaps: if the total is at most k, D is achievable. Achievability is monotonic in D, so binary search D on real numbers until the range is narrower than 10^-6.

  1. lo = 0, hi = the largest gap (no new stations needed for that D).
  2. While hi - lo > 10^-6: mid = (lo + hi) / 2.
  3. needed = sum of floor(gap / mid) over all gaps (stop early once it passes k).
  4. If needed <= k, mid works: hi = mid. Otherwise lo = mid.
  5. Return hi.
class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        double lo = 0, hi = 0;
        for (int i = 0; i + 1 < stations.length; i++) {
            hi = Math.max(hi, stations[i + 1] - stations[i]);
        }
        while (hi - lo > 1e-6) {
            double mid = (lo + hi) / 2;
            if (feasible(stations, k, mid)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        return hi;
    }

    private boolean feasible(int[] stations, int k, double d) {
        long needed = 0;
        for (int i = 0; i + 1 < stations.length; i++) {
            needed += (long) ((stations[i + 1] - stations[i]) / d);
            if (needed > k) {
                return false;
            }
        }
        return true;
    }
}

Edge cases to test

  • Only two stations: the answer is the gap divided by k + 1
  • One huge gap among many tiny ones: all new stations go into the huge gap
  • All gaps equal and k not a multiple of the number of gaps
  • Very large k (10^6), which rules out adding stations one at a time with a linear scan

Hints

Hint 1

New stations inside one gap should always be spread evenly: a gap of length g with c new stations has largest piece g / (c + 1).

Hint 2

Greedy: each new station should go into the gap whose current largest piece is the biggest. A max-heap finds that gap fast.

Hint 3

Flip the question: for a target distance D, how many stations does each gap need? That count only goes down as D grows, so binary search on D.

FAQ

What is the best time complexity for Minimize Max Distance to Gas Station?

Optimal (binary search on the answer) runs in O(n log(W / ε)) time and O(1) extra space. About log2(10^8 / 10^-6) ≈ 47 rounds, each a single pass over the n - 1 gaps (W is the widest gap, ε = 10^-6).

Which pattern does Minimize Max Distance to Gas Station use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Minimize Max Distance to Gas Station?

Yes. Brute force (greedy, linear scan per station) takes O(k·n) time and O(n) space. Keep, for every gap, how many new stations it has received.

Which edge cases should I test for Minimize Max Distance to Gas Station?

Only two stations: the answer is the gap divided by k + 1; One huge gap among many tiny ones: all new stations go into the huge gap; All gaps equal and k not a multiple of the number of gaps; Very large k (10^6), which rules out adding stations one at a time with a linear scan.