Minimize Max Distance to Gas Station

Moderate
0/80
profile
Contributed by
484 upvotes
Asked in company
Urban Company

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.
Detailed explanation ( Input/output format, Notes, Images )
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.


Sample Input 1:
5 4
1 2 3 4 5


Expected Answer:
0.5


Output Printed On Console:
1


Explanation of sample output 1:
k = 4, arr = {1,2,3,4,5} 

One of the possible ways to place 4 gas stations is {1,1.5,2,2.5,3,3.5,4,4.5,5}

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 4 gas stations in such a way that the value of ‘dist’ is lower than this. (Note: 1 will be printed in the output for the correct answer).


Sample Input 2:
10 1
1 2 3 4 5 6 7 8 9 10


Expected Answer:
1


Output Printed On Console:
1


Explanation of sample output 2:
k = 1, arr = {1,2,3,4,5,6,7,8,9,10} 

One of the possible ways to place 1 gas station is {1,1.5,2,3,4,5,6,7,8,9,10} 

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. (Note: 1 will be printed in the output for the correct answer).


Expected Time Complexity
Try solving this in O(n*log(A)), where A is the maximum value in array 'arr'.


Constraints:
2 <= n <= 10^5
1 <= k <= 10^6 
1 <= arr[i] <= 10^9

Time Limit: 1 sec
Hint

What is the most optimal position to place a gas station?

Approaches (3)
Greedy

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
Time Complexity

O(K * N), where ‘N’ is the size of array ‘Arr’ and ‘K’ is the amount of gas stations we are allowed to place.


 

We are iterating via ‘j’ from 1 to ‘K’ and for each ‘j’, we are iterating via ‘i’ from 0 to ‘N - 2’, hence the overall time complexity of this solution is O(K*N).

Space Complexity

O(N), where ‘N’ is the size of array ‘Arr’.
 

We are utilising an array diff of length ‘N-1’ and an array count of length ‘N-1’. Thus the space complexity is linear.

Code Solution
(100% EXP penalty)
Minimize Max Distance to Gas Station
Full screen
Console