Gas Station

Signal

"Find the single valid starting point on a circular route" smells like it needs trying every start — but a single pass with a global feasibility check and a greedy restart rule solves it without brute force.

Approach

First, feasibility: a valid start exists at all iff total gas across every station is at least total cost — otherwise no starting point works, full stop. Given that, walk the stations once with a running tank. Whenever the tank goes negative at station i, no station from the current candidate start through i could have been a valid start either (they'd all run the tank negative by the time they reached i), so reset the candidate start to i + 1 and the tank to 0. The start you land on after the full pass is the answer.

Skeleton

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

Solution

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1

    tank = 0
    start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

Complexity

O(n) time — one pass (plus the O(n) feasibility sum). O(1) space.

Pitfalls

• Skipping the global sum(gas) < sum(cost) feasibility check and just returning whatever start the single pass lands on — the pass always produces some index, but it's only valid when a solution actually exists.
• Trying every starting index and simulating the full circuit for each is correct but O(n²) — the greedy restart works because of a real invariant (any station between a failed start and the failure point is also a failed start), not because "one pass always happens to work."
• The problem guarantees the answer is unique when one exists — don't add logic to handle multiple valid starts.