Gas Station Circular Route — Greedy with Tank Tracking

The problem

Circular route. Start with empty tank at station i. Buy gas[i], drive to i+1 (costs cost[i]). Can you complete the loop?

Naive O(N²)

Try every starting station. Simulate. Too slow for N > 10000.

O(N) greedy

int total = 0, tank = 0, start = 0;
for (int i = 0; i < n; i++) {
  int diff = gas[i] - cost[i];
  total += diff;
  tank += diff;
  if (tank < 0) {
    start = i + 1;
    tank = 0;
  }
}
return total < 0 ? -1 : start;

Why it works

If total gas < total cost, impossible. Otherwise, if you can't reach station i from any start ≤ i, then start > i.