Gas Station

GREEDY · MEDIUM

The problem

n gas stations sit around a circular route. Station i has gas[i] gas, and it costs cost[i] gas to drive from station i to the next station (i + 1) % n. Your car starts with an empty tank at whichever station you pick. Given gas and cost, return the index of the station you must start at to complete the full loop exactly once — or -1 if no starting station works. If a solution exists, it’s guaranteed to be unique.

LeetCode: Gas Station

Solution 1: Brute force — simulate the whole lap from every start

The direct reading of the problem: for every candidate starting station, drive the full circular lap and watch the tank. If it ever dips below zero, that start doesn’t work — move on to the next candidate. The first start that survives the whole lap is the answer.

function canCompleteCircuitBrute(gas, cost) {
  const n = gas.length;
  for (let start = 0; start < n; start++) {
    let tank = 0;
    let ok = true;
    for (let step = 0; step < n; step++) {
      const i = (start + step) % n;
      tank += gas[i] - cost[i];
      if (tank < 0) { ok = false; break; }
    }
    if (ok) return start;
  }
  return -1;
}

Complexity: O(n²) time, O(1) space.

Interactive visualization

Bars show gas[i] − cost[i] (the net gas gained or lost at each station) for a small 5-station example — the same values verified above.

gas = [1, 2, 3, 4, 5] · cost = [3, 4, 5, 1, 2] · net = [-2, -2, -2, 3, 3]

Press Play or Step to begin.

station being tried · reached this lap · tank went negative · full lap completed

Step 0 / 14

Line by line:

The outer loop tries every station as a candidate start — n candidates.
(start + step) % n walks the route circularly: once step pushes past the last station, the index wraps back to 0.
tank += gas[i] - cost[i] is the net change in fuel at each stop — arrive with gas[i] more, leave with cost[i] less to reach the next station.
The moment tank < 0, this candidate is provably impossible and the inner loop bails immediately — but the work already done simulating up to that point is thrown away and redone (possibly overlapping) for the next candidate.

Solution 2: Optimal — one greedy pass, no restarting

Key insight: if the tank goes negative trying to reach station i from candidate start s, then no station between s and i can be the answer either — starting anywhere in that range only means arriving at i with an equal or smaller running tank, since every station from s up to that point contributed a non-negative running total up until it broke. So the moment the tank dips below zero, immediately move the candidate start to i + 1 and reset the tank to 0 — never re-walk the discarded range. One separate running total across the entire circuit answers the yes/no feasibility question: if the total net gas is negative, no start can ever work, full stop.

function canCompleteCircuitOptimal(gas, cost) {
  const n = gas.length;
  let total = 0;
  let tank = 0;
  let start = 0;

  for (let i = 0; i < n; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }

  return total >= 0 ? start : -1;
}

Complexity: O(n) time, O(1) space — every station is visited exactly once, no re-walking.

Interactive visualization

Same 5-station example, same net values — watch how few steps the greedy pass needs compared to Solution 1 above.

gas = [1, 2, 3, 4, 5] · cost = [3, 4, 5, 1, 2] · net = [-2, -2, -2, 3, 3]

Press Play or Step to begin.

station just processed · stations since candidate start · candidate start discarded · winning start's full loop

Step 0 / 12

Line by line:

total accumulates the net gas across the ENTIRE circuit, regardless of any resets — it answers “does a valid start exist at all?”
tank accumulates the net gas since the current candidate start only — it answers “does THIS candidate survive?”
if (tank < 0) — the candidate just failed. start = i + 1 and tank = 0 throw away the whole failed range in O(1), never revisiting it.
total >= 0 ? start : -1 — if the whole circuit’s net gas is negative, no start could ever work, so return -1 regardless of what start holds. Otherwise, the last start the loop settled on is guaranteed correct.

Complexity comparison

Solution	Time	Space
Brute force (simulate every start)	O(n²)	O(1)
Optimal (greedy single pass)	O(n)	O(1)

This is a genuine asymptotic improvement, not just a constant-factor speedup — brute force re-walks the route from scratch for every candidate (up to n stations, n times), while the greedy pass touches each station exactly once, total, across the whole run.

Interview corner

Why is it safe to skip every station between the failed start and the failure point, instead of trying them one at a time?

Say the tank goes negative trying to reach station i starting from s.
For any candidate s' strictly between s and i, the tank arriving at i starting from s' can be at best equal to starting from s — every station from s up to s' contributed a non-negative running sum (otherwise the failure would’ve happened earlier).
Dropping that non-negative prefix only removes fuel that was helping, so s' fails at i too, or fails even earlier. Either way it’s never the answer — safe to skip straight to i + 1.

Why does checking only total >= 0 at the very end correctly decide feasibility, when tank was reset to 0 possibly several times along the way?

total never resets — it’s the sum of every gas[i] - cost[i] across the whole circuit, independent of which candidate is currently active.
If total < 0, the circuit can never be completed from any start, period — there simply isn’t enough total gas for the total cost, so no tank could ever stay non-negative for a full lap.
If total >= 0, the problem’s own guarantee (a solution is unique when one exists) plus the elimination argument above means the last surviving start is exactly that solution.

Why is this the same shape as Kadane’s algorithm (maximum subarray)?

Kadane’s also tracks a running sum that resets to 0 the moment it goes negative, because a negative-sum prefix can never help a future subarray sum.
Here, tank resets the moment it goes negative for the exact same reason — a failing prefix can never help a future candidate start succeed.
The circular (i + 1) % n wraparound and the separate total feasibility check are the only real differences from a plain Kadane’s scan.

Trick question — what does this log?

const stations = ['A', 'B', 'C', 'D', 'E'];
const n = stations.length;
const i = 0;
console.log(stations[(i - 1) % n]);

Answer: undefined, not 'E'.
JavaScript’s % is a remainder operator, not a true mathematical modulo — it keeps the sign of the dividend. (0 - 1) % 5 is -1, not 4.
stations[-1] isn’t the last element (there’s no Python-style negative indexing) — it’s simply undefined.
The fix is ((i - 1) + n) % n, which is always non-negative.
⚠ Trap: this problem’s own (i + 1) % n forward wraparound never hits this bug because i + 1 is never negative — but the instant a variant of this problem asks you to look backward (previous station, previous index), this exact off-by-sign bug is waiting.

Quiz

1. Why does the greedy solution jump the candidate start all the way to i + 1 the moment the tank goes negative, instead of just trying s + 1 next?

Every station between s and i is provably eliminated too — none of them can reach i without also going negative
It’s purely a speed shortcut with no correctness guarantee — it just usually happens to work
The choice of i + 1 vs s + 1 doesn’t affect correctness, only which valid answer gets returned

2. What does the separate total variable track that tank alone couldn’t tell you?

Whether the whole circuit has enough net gas at all — a fact independent of which candidate start is currently active
Nothing — total and tank always hold the exact same value throughout the loop
The index of the very first station that ever failed

3. Why does total < 0 guarantee -1 is correct, no matter which station you start from?

Total net gas across the whole circuit is negative, so no starting point can ever complete a full lap
It doesn’t guarantee that — you’d still need to brute-force check every start to be sure
It only rules out starting at station 0, not the other stations

4. Why is brute force O(n²) while the greedy pass is O(n), given both eventually look at every station?

Brute force re-walks up to n stations for each of the n candidate starts; greedy visits every station exactly once, total
They’re actually the same complexity — O(n) for both
The difference is about space, not time — both are O(n) time

5. Which other well-known pattern does the “reset the running tank to 0 the moment it goes negative” trick mirror?

Kadane’s algorithm for maximum subarray sum
Binary search over a sorted array
Dijkstra’s shortest-path algorithm