1. The Problem
Given a list of gas stations `G` by their distance from a starting point `A`, a car's maximum range `M` on a full tank, and a total distance `D` to a destination `B`, find the minimum number of refueling stops required to complete the journey.
2. The Idea: Greedy Algorithm
This problem can be solved optimally with a greedy approach. The core idea is to always travel as far as possible before making a stop. From your current location, you should look ahead to all the gas stations you can reach with your current tank. To maximize your options for the *next* leg of the journey, it is always optimal to stop at the farthest reachable gas station.
This strategy works because stopping at a closer station provides no advantage; you would simply have less fuel and a shorter range for the subsequent leg, potentially forcing you to make an extra stop later that could have been avoided by going further initially.
3. The Algorithm
- Combine all locations into a single list: `Locations = [0] + G + [D]`. This simplifies boundary conditions.
- Initialize `stops = 0`, `current_pos = 0`, and `i = 0` (an index for the `Locations` array).
- While `current_pos < D`:
- Find the farthest location `farthest_reachable` that can be reached from `current_pos` (i.e., `Locations[j] - current_pos <= M`).
- If `farthest_reachable` is the same as `current_pos`, it's impossible to advance. Return failure.
- Update `current_pos = farthest_reachable`.
- If the new `current_pos` is not the destination `D`, increment `stops`.
- Return `stops`.
4. Complexity Analysis
- Time Complexity: O(n)
- Where `n` is the number of gas stations. Although there appears to be a nested loop structure (a `while` loop containing a search for the farthest station), the index `i` that tracks our position in the `Locations` array only ever moves forward. Each gas station is considered only a constant number of times. Therefore, the algorithm runs in linear time.
- Space Complexity: O(n)
- If we create a new array to store all locations, the space complexity is O(n). This can be optimized to O(1) if we are allowed to modify the input or handle the start/end points with special logic.