Station i gives gas[i]; driving to the next station costs cost[i]. Return the station from which you can complete the circuit with an initially empty tank, or -1. The answer, if it exists, is unique.
Before you code
If total gas is less than total cost, no start works. Otherwise, a start fails exactly when the tank goes negative somewhere, and then no station between the start and that point can work either.
Hints
- Track the total balance and a running tank.
- When the tank goes negative at station i, set the start to i + 1 and reset the tank to 0.
- If the total is non-negative, the last start chosen is the answer.
Production & complexity notes
When solving Gas station on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in When greedy works to reinforce the underlying pattern.
What it practices
Proving a greedy restart rule, from When greedy works.