Coding

Minimize Max Distance to Gas Station

Asked atAArcesium

BloomBerg

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a sorted array arr of size n, containing integer positions of n gas stations on the X-axis, and an integer k, place k new gas stations on the X-axis.

The new gas stations can be placed anywhere on the non-negative side of the X-axis, including non-integer positions.

Let dist be the maximum distance between adjacent gas stations after adding the k new gas stations.

Find the minimum value of dist.

Your answer will be accepted if it is within 1e-6 of the true value.

Input: n = 10, arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10], k = 10 Output: 0.50000 Explanation: One of the possible ways to place 10 gas stations is [1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5, 7, 7.5, 8, 8.5, 9, 9.5, 10]. Thus the maximum difference between adjacent gas stations is 0.5. Hence, the value of dist is 0.5. It can be shown that there is no possible way to add 10 gas stations in such a way that the value of dist is lower than this.

**Input **: n = 10, arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 1 Output: 1.00000 Explanation:

One of the possible ways to place 1 gas station is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].
New Gas Station is at 11.
Thus the maximum difference between adjacent gas stations is still 1.
Hence, the value of dist is 1.
It can be shown that there is no possible way to add 1 gas station in such a way that the value of dist is lower than this.

Input: n = 10, arr= [3, 6, 12, 19, 33, 44, 67, 72, 89, 95], k = 2

10 <= n <= 5000
0 <= arr[i] <= 109
arr is sorted in a strictly increasing order
0 <= k <= 105

cpp

class Solution {
public:
    long double minimiseMaxDistance(vector<int> &arr, int k) {
       
    }
};

java

class Solution {
    public double minimiseMaxDistance(int[] arr, int k) {
        
    }
}

python

class Solution:
    def minimiseMaxDistance(self, arr, k):

javascript

class Solution {
    minimiseMaxDistance(arr, k) {
       
    }
}

csharp

class Solution
{
    public double MinimiseMaxDistance(List<int> arr, int k)
    {
      
    }
}

func minimiseMaxDistance(arr []int, k int) float64 {

}

Stuck? Show a way to structure it+

01Search the maximum allowed adjacent distance between zero and the largest original gap.
02For a candidate distance, count how many new stations each gap requires.
03Shrink the answer range when the total required stations is at most k.
04Stop when the precision tolerance is reached and use ceil for required stations.

Reference answer

Binary-search the answer d, the proposed maximum gap. For an original gap g, the number of new stations needed so every piece is at most d is ceil(g / d) - 1. Sum this across gaps, stopping early if it exceeds k. If at most k stations are required, d is feasible and the upper bound can move down; otherwise move the lower bound up. Start with low = 0 and high = maxGap, and iterate until high - low is below a tighter tolerance than 1e-6, or run a fixed number such as 80 iterations. Return high. Each feasibility check is O(n), so total time is O(n log(maxGap / epsilon)) with O(1) space. Be careful at exact multiples: ceil(g/d)-1 avoids placing an unnecessary station at an existing endpoint.

Then expect these follow-ups

Why is feasibility monotonic in d?
Tests: binary-search proof
How would you construct the station positions?
Tests: solution reconstruction

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question