DSA Tracker

Visualize

Gas Station

time O(n)space O(1)

The insight: if the running tank total from some candidate start turns negative by the time you reach station i, every station between that start and i is also a dead end — starting from any of them just means giving up part of the surplus that got you that far, so they'd run out even sooner. That's why the moment tank dips negative, it's safe to jump the candidate start all the way to i+1 and reset to zero, instead of retrying every in-between station one by one. One linear pass — tank += gas[i]-cost[i], reset on negative — is enough because, as long as total gas >= total cost, exactly one starting point survives every reset and completes the circuit.

Details

Animated on: Given gas and cost arrays for n gas stations arranged in a circle, find the starting station index that allows traveling around the circuit once. Return -1 if impossible.

Problem:Gas StationMedium

Pattern:Greedy Scheduling and Sorting

Greedy

step 1 / 8

1
[0]
2
[1]
3
[2]
4
[3]
5
[4]

Initialize tank=0, start=0, i=0. Total gas = 1+2+3+4+5 = 15, total cost = 3+4+5+1+2 = 15. Tank will track net gain across the circuit.

  • tank=0· arr[0] = 1
  • start=0· arr[0] = 1
  • i=0· arr[0] = 1
Pseudocode
1FUNCTION canCompleteCircuit(gas, cost):
2  set tank = 0 and start = 0
3  FOR i from 0 to length of gas - 1:
4    add gas[i] - cost[i] to tank
5    IF tank < 0:
6      set start = i + 1
7      reset tank = 0
8    END IF
9  END FOR
10  RETURN start if total gas >= total cost, otherwise -1
11END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Initialize tank=0, start=0, i=0. Total gas = 1+2+3+4+5 = 15, total cost = 3+4+5+1+2 = 15. Tank will track net gain across the circuit.
  2. i=0: tank += gas[0]-cost[0] = 1-3 = -2. tank = -2 < 0 → reset. start = i+1 = 1, tank = 0.
  3. i=1: tank += gas[1]-cost[1] = 2-4 = -2. tank = -2 < 0 → reset. start = i+1 = 2, tank = 0.
  4. i=2: tank += gas[2]-cost[2] = 3-5 = -2. tank = -2 < 0 → reset. start = i+1 = 3, tank = 0.
  5. i=3: tank += gas[3]-cost[3] = 4-1 = 3. tank = 3 (>=0, no reset). Continue.
  6. i=4: tank += gas[4]-cost[4] = 5-2 = 3. tank = 3+3 = 6 (>=0, no reset). Loop ending.
  7. Loop finished. total gas(15) >= total cost(15), so a solution exists. Final start = 3 (index 3).
  8. Confirm by tracing the actual circuit from station 3: tank=4-1=3 → +5-2=6 → wrap to station0: +1-3=4 → +2-4=2 → +3-5=0. Never negative — circuit completes. Answer: start=3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Gas Station in the editorAll Greedy problemsBack to roadmap