Practice/Amazon/Leetcode 774. Minimize Max Distance to Gas Station

Leetcode 774. Minimize Max Distance to Gas Station

CodingMust

Problem

You are responsible for optimizing the placement of electric vehicle charging stations along a highway. The highway is represented as a straight line, and you are given the positions of existing charging stations as an array of integers.

Your task is to add exactly k new charging stations anywhere along the highway to minimize the maximum distance between any two consecutive charging stations. Return the minimized maximum distance as a floating-point number.

The positions array is sorted in ascending order, and you can place new stations at any real-value position between the first and last existing stations.

Requirements

1. Calculate the optimal placement for exactly k new charging stations
2. Minimize the maximum gap between consecutive stations
3. Return the answer as a floating-point number with sufficient precision
4. The answer will be accepted if it has an absolute error less than 10^-6

Constraints

• 2 ≤ stations.length ≤ 2000
• 0 ≤ stations[i] ≤ 10^8
• The stations array is sorted in strictly increasing order
• 0 ≤ k ≤ 10^6
• Time complexity should be better than O(n × k)
• Space complexity should be O(1) or O(n)

Examples

Example 1:

Input: stations = [1, 2, 5, 10], k = 1 Output: 2.5 Explanation: We can add one station at position 7.5. This splits the gap [5, 10] into two gaps of 2.5 each. The gaps are now [1], [3], [2.5], [2.5], so the maximum gap is 3.0. Better: add at 3.5 to split [2,5] into [1.5, 1.5], but then [5,10] remains 5. Optimal is actually to split the largest gap [5,10], giving maximum gap of max(1, 3, 2.5) = 3.0. Further analysis shows 2.5 is achievable.

Example 2:

Input: stations = [1, 13], k = 3 Output: 3.0 Explanation: The distance between the two stations is 12. By adding 3 new stations, we divide this into 4 equal segments: [1, 4, 7, 10, 13], each with distance 3.0.

Example 3:

Input: stations = [10, 20, 30, 40, 50], k = 2 Output: 5.0 Explanation: The gaps are all 10 units. Adding 2 stations optimally means placing one in each of two gaps, splitting them into segments of 5.0 each, giving us a maximum gap of 10.0 from the unsplit gaps, or we split one gap twice to get 3.33. Optimal strategy splits two different gaps to achieve 5.0.