Gas Station

Let delta[i] = gas[i] - cost[i]. If the sum of all deltas is negative, no starting station can complete the circuit, so return -1.

Otherwise scan from left to right with start = 0 and tank = 0. Add each delta[i] to tank. If tank becomes negative at station i, the current start cannot reach i + 1. More importantly, no station between the current start and i can work either: each such station begins with an even smaller remaining prefix because it skips a prefix whose accumulated balance was non-negative before the failure. Set start = i + 1 and reset tank = 0.

The non-negative total guarantees that the candidate left after the final reset can complete the wraparound portion. The scan is O(n) time and O(1) space. This is stronger than trying every start, which can take O(n^2). Be explicit about the proof behind the reset; the implementation is short, but the invariant is what the interviewer is evaluating.