Gas Station
Problem statement
There are n gas stations arranged in a circle. Station i has gas[i] units of fuel available, and it costs cost[i] units of fuel to drive from station i to the next one going clockwise.
You start with an empty tank at one station of your choosing. Find a starting station from which you can make it all the way around the circle back to where you started, or return -1 if no such station exists. If a valid starting station exists, it's guaranteed to be the only one.
Examples
Example 1
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Starting at station 3, the tank never goes negative on the way around: fill up 4, spend 1 to reach station 4 (net +4), fill up 5, spend 2 to reach station 0 (net +7), fill up 1, spend 3 to reach station 1 (net +6), fill up 2, spend 4 to reach station 2 (net +5), fill up 3, spend 5 to get back to station 3 (net +3, exactly enough).
Example 2
Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: The total gas available (2+3+4=9) is less than the total cost of driving the whole circle (3+4+3=10), so no starting station can possibly make it all the way around.
Hints
Approach
Optimal: One-pass greedy
Intuition
The second pass in the "better" approach only exists to check one fact: does the total gas across the whole circuit cover the total cost? That's a single sum comparison you can compute in the very same pass that finds the candidate starting station — there's no need to walk the circle a second time just to confirm it. Track the running total (never reset) alongside the running tank (reset on failure); at the end, the total tells you directly whether a solution exists at all.
Steps
- Set
total = 0,tank = 0, andstart = 0. - Walk
ifrom 0 to n-1: computediff = gas[i] - cost[i], and add it to bothtotalandtank. - If
tankgoes negative, this candidate has failed — setstart = i + 1and resettankto 0 (buttotalkeeps accumulating, uninterrupted). - Once the loop finishes,
totaltells you everything: if it's negative, no station works, so return -1. - Otherwise,
startis guaranteed to be the one valid starting station — return it directly, no second pass required.
Dry run
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
| i | diff | total | tank | tank < 0? | start after |
|---|---|---|---|---|---|
| 0 | -2 | -2 | -2 | yes | 1 |
| 1 | -2 | -4 | -2 | yes | 2 |
| 2 | -2 | -6 | -2 | yes | 3 |
| 3 | +3 | -3 | 3 | no | 3 |
| 4 | +3 | 0 | 6 | no | 3 |
total ends at 0 (≥ 0), so the answer is start = 3 — no second pass needed to confirm it.
Edge cases: gas = [2, 3, 4], cost = [3, 4, 3] gives total = -1 at the end, so the function returns -1 directly, even though a "candidate" start value was tracked along the way.
Complexity
Time O(n) - a single pass over the stations; no second pass is needed.
Space O(1) - a running tank, a running total, and a candidate index.
class Solution:
def canCompleteCircuit(self, gas, cost):
n = len(gas)
total = 0
tank = 0
start = 0
for i in range(n):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1
if __name__ == "__main__":
print(Solution().canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(Solution().canCompleteCircuit([2, 3, 4], [3, 4, 3]))RecapThe whole problem in a few lines, for the night before
- Spot it: "find a starting point on a circular route where a running balance never goes negative"
- Idea: reset your candidate start to the very next station the moment the running tank goes negative; the total gas vs. total cost comparison alone tells you if any solution exists
- Cost: O(n) time, O(1) space (one-pass greedy); still O(n) time with a two-pass verify step; O(n^2) for the brute-force simulate-every-start approach
- Trap: forgetting the feasibility check (total gas < total cost) and returning a "candidate" start that doesn't actually work
Interview follow-ups
What if the car had a limited tank capacity instead of an unlimited one?
The single running-tank trick stops being enough, because now excess fuel can be wasted rather than carried forward indefinitely. Simulating with a capped tank generally needs trying each candidate starting point directly (or a more careful greedy that also tracks when the tank would overflow), which pushes the approach back toward O(n^2) unless the specific cap values allow a further trick.
The gas and cost values arrive as a live stream (stations reporting in real time) rather than a fixed array you can read twice.
The one-pass optimal approach already works well here, since it never needs a second read — track
totalandtankexactly as before as each station reports in, and reset the candidate start whenevertankgoes negative. Once the stream ends, the sametotal >= 0check gives the answer with no need to have buffered the whole stream.
Frequently asked questions
If starting from station s fails because the tank goes negative at station i, then any station between s and i would arrive at station i with the same or less fuel than starting at s did — they lose whatever surplus s had already banked by the time they'd reach i. So none of them could possibly succeed either, and it's safe to jump the candidate straight to i + 1 without checking them individually.
The circuit is a fixed loop, so the total fuel gained and the total fuel spent don't depend on where you start — only the order you encounter the ups and downs changes. If the total gas is less than the total cost, no ordering can make the sum work out, so it's impossible everywhere. If the total gas is at least the total cost, it's a mathematical guarantee (not just a heuristic) that some starting point makes the running tank stay non-negative the whole way around.
It mirrors a real capacity-planning question: given a rotation of maintenance windows or batch jobs, each producing or consuming some budget (CPU credits, a rate-limit allowance, a deploy budget), is there a starting point in the cycle from which the running balance never goes negative? The greedy "reset on going negative" technique is the same one used to find such a safe starting point in scheduling problems.
The problem guarantees a unique answer if one exists, so yes for this problem specifically — but the same greedy technique, run without that guarantee, would only be certain to find a valid starting point, since it never explicitly rules out the possibility of multiple valid ones existing elsewhere in the circuit.