Back to Problem
Official 1367 views

Editorial: Gas Station Circuit

by admin ·

3

1 Intuition

If the total gas covers the total cost, a valid start exists — and it can't be any station you fail to pass when starting earlier.

2 Approach

Scan once; whenever the tank goes negative, restart from the next station.

3 Complexity Analysis

Time O(n), Space O(1).

4 Solution Code 

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        start = tank = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start, tank = i + 1, 0
        return start

5 Code Walkthrough

The reference solution below implements the approach step by step.