Last Updated: 16 Feb, 2023

Minimize Max Distance to Gas Station

Moderate

Asked in company

Solve now

Problem statement

You are given a sorted array ‘arr’ of length ‘n’, which contains positive integer positions of ‘n’ gas stations on the X-axis.

You are also given an integer ‘k’.

You have to place 'k' new gas stations on the X-axis.

You can place them anywhere on the non-negative side of the X-axis, even on non-integer positions.

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

Find the minimum value of dist.

Example:

Input: ‘n' = 7 , ‘k’=6, ‘arr’ = {1,2,3,4,5,6,7}.

Answer: 0.5

Explanation:
We can place 6 gas stations at 1.5, 2.5, 3.5, 4.5, 5.5, 6.5. 

Thus the value of 'dist' will be 0.5. It can be shown that we can't get a lower value of 'dist' by placing 6 gas stations.

Note:

You will only see 1 or 0 in the output where:
  1 represents your answer is correct.
  0 represents your answer is wrong. 
Answers within 10^-6 of the actual answer will be accepted.

Input format:

The first line contains two integers, ' n' and 'k', representing the size of the array 'arr' and the number of additional gas stations you need to place.
The second line contains 'n' integers, denoting the array 'arr' elements.

Output Format:

Return the minimum value of 'dist'.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function. 1 will be printed for answers with an error less than 10^-6 from the actual answer and 0 otherwise.

Solve now

Approaches

01 Approach

Approach:

The best position to place a gas station is between the gas stations with the current largest distance between them. So we can repeatedly add a gas station in the current largest interval. To do so we maintain two arrays ‘diff’ and ‘count’ of length ‘N-1’. In the ‘diff’ array we store the distance between the two gas stations in the current interval and in the count array we store the number of gas stations added in the current interval. Thus, the current maximum interval for a gas station would be the interval with the maximum value of ‘diff[i] / count[i]’ .

Algorithm:

Initialise array ‘diff’ of length N-1 with 0s
for ‘i’ from 0 to N-2:
- diff[i] = arr[i+1] - arr[i]
Initialise array count of length N-1 with 1s
Initialise variable ans=0
for ‘j’ from 1 to ‘K’:
- best = 0
- for ‘i’ from 0 to ‘N - 2’:
  - if( diff[i] * count[best] > diff[best] * count[i] )
    - best = i

count[best]++
for ‘i’ from 0 to ‘N-2’:
- ans = max(ans, diff[i] / count[i])
return ans

Solve now

02 Approach

Approach:

Following the approach from the greedy method, instead of iterating through all the intervals for every gas station, we can maintain a priority queue of pairs {diff[i] / count[i], i} for the ‘ith’ interval sorted in a decreasing order. Then we can choose the interval at the top of the queue, delete it from the queue. Then we increment the count of the ‘ith’ interval and insert {diff[i] / count[i] , i} back into the queue.

Algorithm:

Initialise array ‘diff’ of length ‘N-1’ with 0s
Initialise array count of length ‘N-1’ with 1s
Initialise a priority queue ‘pq’ sorted in decreasing order
for ‘i’ from 0 to N-2:
- diff[i] = arr[i+1] - arr[i]
for ‘i’ from 0 to N-2:
- pq.push({diff[i] / count[i], i})
Initialise variable ans=0
for ‘j’ from 1 to ‘K’:
- best = pq.top()
- i = best.second
- pq.pop()
- count[i]++
- pq.push({diff[i] / count[i], i})
ans = pq.top().first
return ans

Solve now

03 Approach

Approach:

Let’s say there exists a value ‘D’ of ‘Dist’ such that for a value ‘d’ < ‘D’ it is not possible to make the maximum distance between all the adjacent gas stations equal to ‘d’ by adding at most ‘K’ gas stations. As we can see this is a monotonic function and thus we can binary search on it. So we binary search on the value of ‘D’ and check if it’s possible to achieve this value of ‘Dist’ by adding at most ‘K’ gas stations.

Algorithm:

Initialise variable D=0
Initialise variables lo = 0 , hi = 1e9
while(hi - lo > 1e-6)
- used =0
- mid = (hi + lo) / 2.0
- for ‘i’ from 0 to ‘N-2’:
  - used += (arr[i+1]-arr[i]) / mid
- if(used>K)
  - lo = mid
- else
  - hi = mid
  - D = mid
return D

Solve now