Gas Station
Understanding the Problem
We have gas stations arranged in a circle. At each station, we pick up some gas and spend some gas to reach the next station. We need to find a starting station where we can complete the full loop without running out of gas at any point.
Two things make this interesting. First, the route is circular, so after station n-1 we wrap back to station 0. Second, we start with an empty tank, so the very first station we visit must give us enough gas to at least reach the next one.
At each station, what matters is the net gain: gas[i] - cost[i]. If the net gain is positive, we gain fuel at that station. If it's negative, we lose fuel. The whole problem reduces to one question: can we find a starting point where the running sum of net gains never drops below zero?
Key Constraints:
1 <= n <= 10^5-- With up to 100,000 stations, an O(n^2) brute force that tries every starting point and simulates the full trip would be 10^10 operations, which is too slow. We need O(n) or O(n log n).0 <= gas[i], cost[i] <= 10^4-- Values are non-negative, so no tricky negative gas amounts. The net gain at each station ranges from -10^4 to +10^4.- The solution is guaranteed to be unique if it exists, so the greedy approach below never has to break ties or choose between multiple valid answers.
Approach 1: Brute Force
Intuition
Try every station as a potential starting point. For each candidate, simulate the full trip around the circuit and check if the tank ever drops below zero.
At station i, we pick up gas[i] and spend cost[i] to drive to the next station. If at any point the tank goes negative, this starting point fails and we move on to the next one.
Algorithm
- For each station
ifrom 0 ton - 1: - Set
tank = 0. - Starting at station
i, visit allnstations in circular order. - At each station
j, addgas[j]and subtractcost[j]. - If
tankdrops below zero at any point, break and try the next starting station. - If we complete all
nstations without the tank going negative, returni. - If no starting station works, return
-1.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n starting stations, we simulate a trip that visits up to n stations.
- Space Complexity: O(1). Only a few variables for the tank and loop counters.
This is too slow for n up to 10^5. When we start at station i and fail at station j, we discard everything we learned and start over at i+1. The next approach uses that failure to skip ahead instead.
Approach 2: Greedy (Single Pass)
Intuition
One observation collapses the problem into a single pass. Start at station i and drive forward. If the tank drops below zero when we arrive at station j, then no station between i and j can be a valid start either.
Here is why. Starting at i, when we reached any intermediate station k between i and j, the tank was non-negative (otherwise we would have failed earlier at k). So station k was reached with some leftover gas carried from stations i through k-1. If even that leftover gas couldn't carry us past j, then starting at k with an empty tank cannot either.
So when the tank goes negative at j, we skip every station from i to j and try j + 1 as the next candidate. That turns the O(n^2) brute force into O(n).
The algorithm tracks two values at once: a totalGain that sums every net gain to decide whether any solution exists, and a currentTank with a start pointer that locates the actual starting station using the skip-ahead rule.
The skip-ahead rule finds the only candidate that could work, but it doesn't by itself prove that candidate completes the loop. That is what totalGain settles. If the sum of all gas[i] - cost[i] is negative, there isn't enough fuel for the full circuit and no start works, so we return -1.
When totalGain >= 0, the final start is valid. The skip-ahead rule guarantees the tank never goes negative on the segment from start to the last station (any drop would have moved start forward). The stations before start form a prefix whose net gain is negative, so the remaining stations from start onward have a net gain of at least the absolute value of that negative prefix. That surplus covers the wrap-around back to start, which is exactly the prefix we skipped.
Algorithm
- Initialize
totalGain = 0,currentTank = 0, andstart = 0. - For each station
ifrom 0 ton - 1: - Compute the net gain:
gain = gas[i] - cost[i]. - Add
gainto bothtotalGainandcurrentTank. - If
currentTank < 0, the current candidate start can't work. Setstart = i + 1and resetcurrentTank = 0. - After the loop, if
totalGain >= 0, returnstart. Otherwise return-1.
Example Walkthrough
Code
- Time Complexity: O(n). A single pass through the array. Each station is visited exactly once.
- Space Complexity: O(1). Only three integer variables: totalGain, currentTank, and start.