AlgoMaster Logo

Gas Station

Last Updated: March 29, 2026

medium
4 min read

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.

The key observation is that 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 entire problem boils down to: 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. This is a strong hint that a greedy approach works, because we don't need to break ties or handle multiple valid answers.

Approach 1: Brute Force

Intuition

The most straightforward idea is to 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

  1. For each station i from 0 to n - 1:
    • Set tank = 0.
    • Starting at station i, visit all n stations in circular order.
    • At each station j, add gas[j] and subtract cost[j].
    • If tank drops below zero at any point, break and try the next starting station.
    • If we complete all n stations without the tank going negative, return i.
  2. If no starting station works, return -1.

Example Walkthrough

1Try start=0: tank=0, gain=-2, tank=-2 < 0, fail
0
start
-2
1
-2
2
-2
3
3
4
3
1/5

Code

This approach works but is too slow for the constraint of n up to 10^5. When we start at station i and fail at station j, we throw away everything we learned and start fresh at i+1. What if we could skip ahead instead?

Approach 2: Greedy (Single Pass)

Intuition

Here's the key insight that makes this problem solvable in one pass. Suppose we start at station i and drive forward, but the tank drops below zero when we arrive at station j. What can we conclude?

If station i couldn't carry us past station j, then no station between i and j could either. Why? Because starting at station i, when we reached any intermediate station k (between i and j), our tank was non-negative (otherwise we would have failed earlier at k). So station k had a head start, it had some leftover gas from the earlier stations. If even with that extra gas we couldn't get past j, starting fresh at k with an empty tank would be even worse.

This means we can skip all stations from i to j and try j + 1 as our next candidate. This transforms the O(n^2) brute force into O(n).

The algorithm tracks two things simultaneously: a totalGain to check feasibility (does enough gas exist overall?), and a currentTank with a start pointer to find the actual starting station using the skip-ahead strategy.

Algorithm

  1. Initialize totalGain = 0, currentTank = 0, and start = 0.
  2. For each station i from 0 to n - 1:
    • Compute the net gain: gain = gas[i] - cost[i].
    • Add gain to both totalGain and currentTank.
    • If currentTank < 0, the current candidate start can't work. Set start = i + 1 and reset currentTank = 0.
  3. After the loop, if totalGain >= 0, return start. Otherwise return -1.

Example Walkthrough

1Initialize: totalGain=0, currentTank=0, start=0
0
start
-2
i
1
-2
2
-2
3
3
4
3
1/6

Code