The Gas Station problem finds the starting gas station's index from which you can travel around the circular circuit once in the clockwise direction without running out of gas, given gas levels and travel costs.

Verify if total gas >= total cost first. If yes, sweep stations from 0. Keep a running gas tank balance: if the tank drops below 0 at station i, the start station cannot be between the previous start and i. Reset the start station search to i + 1.

A valid start index is guaranteed to exist and complete the circuit once we identify a start index j that maintains a positive running tank for the rest of the array scan.

Proof by contradiction: if the tank goes negative at station i starting from j, no station between j and i can be a valid starting station because they would arrive at i with less than or equal gas.