Minimize Max Distance to Gas Station
HardBinary search on a real number
Guess the biggest allowed gap between stops, then add stations to see if you can keep gaps that small.
The idea
Adding k stations, the largest gap you can guarantee is monotone. Binary search over real gap values until the required stations fit in k.
lo
hi
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
Step 1 of 6. Stations at [0,10,20,30], add 3. Minimize the largest gap (integer search). Values: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Pointers: lo at index 0, hi at index 9.
1/6
Optimal
timeO(n log(range/ε))spaceO(1)
Stop at a tiny epsilon.
1let lo = 0, hi = maxGap;2while (hi - lo > 1e-6) {3 const mid = (lo + hi) / 2;4 if (stationsNeeded(dist, mid) <= k) hi = mid;5 else lo = mid;6}7return hi;Input
- array
- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Memory
- lo
- = 0 [1]
- hi
- = 9 [10]
- mid
- —
- needed
- —
Output
- needed
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 9
- Output:
- 0.500
- Explanation:
- Nine gaps of 1; one extra station in each halves every gap to 0.5.
Example 2
- Input:
- stations = [1, 2, 3, 4, 5], k = 4
- Output:
- 0.500
- Explanation:
- Four gaps of 1, four stations to place — one each, so 0.5.
Example 3
- Input:
- stations = [3, 6, 12, 19, 33, 44, 67], k = 5
- Output:
- 14.000
- Explanation:
- The 23-wide gap 44→67 is the binding one; two extra stations bring it to ~7.7, and the 14-wide 19→33 becomes the worst left.
Practice this problem:LeetCode (premium)(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.