Gas Station

Problem

There are n gas stations along a circular route. Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Examples

The brute-force approach

Try starting at every station. Simulate the trip around the circuit and check if you ever run out of gas.

for start in range(n):
    tank = 0
    for i in range(n):
        station = (start + i) % n
        tank += gas[station] - cost[station]
        if tank < 0: break
    else: return start
return -1

O(n²) — simulating from each start takes O(n).

Spotting the pattern

This is a Greedy problem. The key question to ask yourself:

If you're traveling from station s and you run out of gas at station k, why can't any station between s and k be the valid starting station?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.