Shortest Longest Gap After New Stations
MediumBinary Search
Problem
Charging stations stand along a highway at the integer kilometre marks stations, sorted in strictly increasing order. The operator can build k more stations at any integer marks between the first and the last existing station.
Return the smallest possible value of the longest distance between two consecutive stations after building at most k new ones.
Example 1
- Input:
- stations = [0, 10], k = 2
- Output:
- 4
New stations at 4 and 8 leave gaps 4, 4, 2. With gaps of at most 3 you would need three new stations.
Example 2
- Input:
- stations = [1, 4, 9, 10], k = 2
- Output:
- 3
The gaps are 3, 5 and 1. One station at 7 splits the 5 into 3 and 2.
Example 3
- Input:
- stations = [0, 10], k = 1
- Output:
- 5
Constraints
- 2 ≤ stations.length ≤ 10^5
- 0 ≤ stations[i] ≤ 10^9, strictly increasing
- 0 ≤ k ≤ 10^9
Hint
Show the first hint
Fix a target D for the longest gap. How many new stations does one gap of length g need to respect it?
Walkthrough
How to approach it
01Clarify before coding
- Must new stations sit at integer marks? Yes, so the answer is an integer.
- Must all k stations be used? No, at most k.
- Can stations be built outside the current span? It would never help, so no.
02Brute force
Repeatedly add a station to the middle of the currently longest gap (a max-heap of gaps), k times.
Cost: O(k log n) with a heap, and halving the longest gap greedily is not even optimal: splitting a gap of 9 with two stations should give 3, 3, 3, not 4, 2, 3 after successive halvings.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.