Frontend Beauty
ESC

Type to search the knowledge base.

Gas Station

Circular gas stations — if total gas ≥ cost a unique start exists; one-pass track tank and reset start on negative.

intermediate3 min read
  • dsa
  • greedy
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

n stations in a circle. gas[i] fuel at station i, cost[i] to go to next. Start with empty tank; find a starting index that completes the circuit, or -1. Guaranteed unique if exists.

gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
→ 3

Brute

Try each start, simulate full circle. O(n²).

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

Optimal greedy O(n)

Facts:

  1. If sum(gas) < sum(cost) → impossible.
  2. If total ≥ 0, exactly one valid start (unique).
  3. If you run out going from start toward i, no station in (start, i] can be the answer — the deficit only got worse. Next candidate is i+1.
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0;
  let tank = 0;
  let start = 0;

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

  return total < 0 ? -1 : start;
}
Time O(n)
Space O(1)

Walk sample

i diff tank start
0 -2 -2 → reset 1
1 -2 -2 → reset 2
2 -2 -2 → reset 3
3 +3 3 3
4 +3 6 3

total = 0 ≥ 0 → start 3.

Edge cases

  • Single station with gas ≥ cost
  • All zeros
  • Valid start at index 0
  • total == 0 with non-trivial path

Common mistakes

  • Forgetting total check
  • Modular simulation every start
  • Restarting at i instead of i+1

Interview delivery

  1. Circle + unique start.
  2. Brute O(n²).
  3. Total sum + reset start.
  4. Prove skip interval briefly.
  5. O(n)/O(1).

Mental model

Think cumulative fuel delta around the circle. If total delta is negative, impossible. If non-negative, the unique start is just after the worst prefix deficit — implemented by resetting the candidate whenever the running tank goes negative.

Why skipped stations can’t work

If you can’t reach i+1 from start, any start in between still faces the same remaining road with less leftover fuel than when you left start. Hence jump to i+1.

Out-loud answer

“One pass: track total and tank deltas. On tank < 0 reset start to i+1 and tank to 0. After loop, total < 0 → -1 else start. O(n)/O(1). Brute is try each start O(n²).”

Further reading