Time Complexity: O(k*n) + O(n), n = size of the given array, k = no. of gas stations to be placed.

Space Complexity: O(n-1) as we are using an array to keep track of placed gas stations.

Better Approach

Algorithm

Intuition

In the previous approach, for every gas station, we were finding the index i for which the distance between arr[i+1] and arr[i] is maximum. After that, our job was to place the gas station. Instead of using a loop to find the maximum distance, we can simply use the heap data structure i.e. the priority queue.

Approach

First, we will declare an array ‘howMany[]’ of size n-1, to keep track of the number of placed gas stations and a priority queue that uses max heap.
We will insert the first n-1 indices with the respective distance value, arrr[i+1]-arr[i] for every index.
Next, using a loop we will pick k gas stations one at a time.
Then we will pick the first element of the priority queue as this is the element with the maximum distance. Let’s call the index ‘secInd’.
Now we will place the current gas station at ‘secInd’(howMany[secInd]++) and calculate the new section length, new_section_length = initial_section_length / (number_of_stations_ inserted+1) = (arr[secInd+1] - arr[secInd]) / (howMany[i] + 1)
After that, we will again insert the pair into the priority queue for further consideration.
After performing all the steps for k gas stations, the distance at the top of the priority queue will be the answer as we want the maximum distance.

Code