Minimize Maximum Distance Between Gas Stations - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a sorted array of integers representing the positions of existing gas stations along a road. You are also given an integer k, which represents the number of additional gas stations you are allowed to add anywhere between the existing ones.

Your task is to minimize the maximum distance between any two adjacent gas stations after placing the k new stations optimally.

Return the smallest possible maximum distance between gas stations after the optimal placement, rounded to 6 decimal places if required.

Examples❯

Gas Stations k Minimized Max Distance Description
[1, 2, 3, 4, 5] 1 1.000000 All gaps are equal (1), adding 1 station doesn’t improve max gap
[1, 2, 3, 4, 5] 2 0.666667 We can split two of the 1-length gaps to reduce max gap
[10, 20, 30] 1 10.000000 We split either gap [10,20] or [20,30], max gap becomes 10
[10, 30] 2 6.666667 Gap is 20, splitting into 3 parts gives max 6.66
[0, 100] 9 10.000000 We can add 9 stations to divide 100 into 10 segments
[0, 100] 0 100.000000 No stations added, max distance is the initial gap
[] 2 0.000000 No stations exist, no meaningful distance to minimize
[5] 3 0.000000 Only one station means no gaps, so max distance is 0

Solution❯

Understanding the Problem

You're given an array representing the positions of gas stations along a highway. The goal is to add k additional gas stations in such a way that the maximum distance between any two adjacent gas stations becomes as small as possible.

Why is this important? Imagine you're driving, and there's a really long stretch without a gas station. That’s uncomfortable and risky. So, if you could add a few more stations, where would you place them? Intuitively, you'd want to place them in the longest stretches — that’s what this problem is all about.

Step-by-Step Solution with Example

Step 1: Observe the distances

Let’s take an example: stations = [1, 5, 10] and k = 1. This means there are gas stations at positions 1, 5, and 10, and you're allowed to add 1 more.

The current gaps are:

  • Between 1 and 5: distance 4
  • Between 5 and 10: distance 5

So, the largest gap is 5. We want to insert a station such that the largest gap after insertion is minimized.

Step 2: Use Binary Search on the answer

Instead of trying all possible placements (which is slow), we can use binary search. The idea is: if we guess a maximum allowed distance d, can we split all the existing gaps using ≤ k stations so that no segment exceeds d?

Step 3: Check if a guess is valid (Greedy check)

For each gap between two stations, say of length len, we can divide it into ceil(len / d) parts. That means we’d need ceil(len / d) - 1 extra stations in that gap.

We repeat this for every gap and count the total stations needed. If it's ≤ k, then our guess d is valid.

Step 4: Perform the binary search

We search for the smallest possible d using binary search. Start with low = 0 and high = max_gap. While high - low > 1e-6, compute mid and check if it’s possible. Adjust the search bounds accordingly.

Step 5: Return the answer

After the binary search ends, low (or high) will hold the minimum possible maximum distance between any two stations after placing k new ones.

Edge Cases

  • No stations: If the input array is empty, there’s nothing to minimize. Return 0.000000.
  • Only one station: No gaps exist, so return 0.000000.
  • k = 0: You can't add any new station. So, the maximum distance is just the biggest gap between existing stations.
  • Large k: If you have many stations to add, you can split the longest gaps into very small chunks, bringing the max distance down significantly.

Finally

This problem is a classic case of using binary search on the answer — a clever technique when the answer is a real number instead of an integer. By combining binary search with greedy checking, we efficiently minimize the largest distance between stations. It's not about equalizing all distances but about shrinking the worst one.

Always remember to handle edge cases before diving into implementation, and use precision comparisons carefully when working with floating-point numbers.

Algorithm Steps❯

  1. Initialize low = 0 and high = max(arr[i+1] - arr[i]).
  2. While high - low > 1e-6:
  3. → Compute mid = (low + high) / 2.
  4. → Check if it's possible to place ≤ k stations so that max distance ≤ mid.
  5. → If yes, update high = mid.
  6. → Else, update low = mid.
  7. Return high (smallest valid max distance).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <math.h>

int isPossible(int arr[], int n, int k, double dist) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        double gap = arr[i+1] - arr[i];
        count += (int)(gap / dist);
    }
    return count <= k;
}

double minimizeMaxDistance(int arr[], int n, int k) {
    double low = 0.0, high = 0.0, eps = 1e-6;
    for (int i = 0; i < n - 1; i++) {
        double gap = arr[i+1] - arr[i];
        if (gap > high) high = gap;
    }
    while (high - low > eps) {
        double mid = (low + high) / 2;
        if (isPossible(arr, n, k, mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return round(high * 1000000) / 1000000;
}

int main() {
    int arr[] = {1, 2, 8};
    int k = 1;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Minimum Max Distance: %.6f\n", minimizeMaxDistance(arr, n, k));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n × log(max_gap/eps))We perform binary search over precision range and for each guess, count stations in O(n).
Average CaseO(n × log(max_gap/eps))Each step of binary search tests feasibility by iterating through the array.
Worst CaseO(n × log(max_gap/eps))In the worst case, we perform many precision steps, each involving scanning the entire array.

Space Complexity❯

O(1)

Explanation: No extra space is used apart from a few variables for binary search and counters.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...