LeetCode 134: Gas Station

Problem Restatement

There are n gas stations arranged in a circle.

At station i:

The last station connects back to station 0.

We start with an empty tank at one station of our choice. The tank has unlimited capacity.

Return the starting station index if we can travel around the circuit once in clockwise order. If this is impossible, return -1.

If a solution exists, LeetCode guarantees that it is unique. The problem constraints include equal-length gas and cost arrays, 1 <= n <= 10^5, and non-negative gas and cost values.

Examples

Example 1:

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Output:

3

Start at station 3.

Walk through:

We return to station 3, so the answer is 3.

Example 2:

gas  = [2, 3, 4]
cost = [3, 4, 3]

Output:

-1

The total gas is:

2 + 3 + 4 = 9

The total cost is:

3 + 4 + 3 = 10

There is not enough gas overall, so completing the circuit is impossible.

Input and Output

Function shape:

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        ...

First Thought: Try Every Starting Station

The brute force idea is simple.

For each station start:

1. Set tank = 0.
2. Travel through all n stations.
3. At each station, add gas[i] and subtract cost[i].
4. If tank ever becomes negative, this start fails.
5. If we finish all n moves, return start.

This costs O(n^2) in the worst case because we may simulate almost the whole circuit from many starting points.

Since n can be large, we need a linear solution.

Key Insight

For each station, define the net gain:

gain[i] = gas[i] - cost[i]

If the total gain across all stations is negative, no solution exists.

That means:

sum(gas) < sum(cost)

So we return -1.

If the total gain is non-negative, there is enough fuel overall.

Now we need to find the correct starting index.

The greedy rule is:

If we start at start and the tank becomes negative at station i, then none of the stations from start through i can be a valid start.

So the next possible start is i + 1.

Why We Can Skip Failed Starts

Suppose we start at station start.

The tank stays non-negative until station i, but after station i it becomes negative.

That means the total gain from start to i is negative.

Now consider any station k between start and i.

When starting from start, the tank before reaching k was non-negative.

So if we start from k, we remove some helpful non-negative prefix fuel.

The remaining segment from k to i cannot do better than the failed journey from start to i.

Therefore, k also cannot be a valid start.

So after a failure at i, we safely move start to i + 1.

This is the whole greedy argument.

Algorithm

Initialize:

total = 0
tank = 0
start = 0

Then scan each station i from left to right.

At each station:

diff = gas[i] - cost[i]

Add diff to both total and tank.

If tank < 0, then the current candidate start fails.

So:

start = i + 1
tank = 0

After the scan:

1. If total < 0, return -1.
2. Otherwise, return start.

Correctness

If total < 0, the sum of all gas is smaller than the sum of all travel costs. No starting station can create extra gas, so completing the circuit is impossible. Returning -1 is correct.

Now suppose total >= 0.

During the scan, whenever tank becomes negative at station i, the current candidate start cannot complete the route from start to i + 1.

Every station between start and i also fails as a candidate, because each of those starts has no more fuel available on the segment ending at i than the failed attempt from start.

Therefore, discarding all candidates from start through i is safe.

The algorithm only advances start after proving that all earlier candidates in that failed block cannot work.

Since the total gas is enough overall, at least one valid start exists. The remaining candidate after all failed blocks is the valid starting station.

Therefore, the algorithm returns the correct index.

Complexity

Let n = len(gas).

Implementation

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = 0
        tank = 0
        start = 0

        for i in range(len(gas)):
            diff = gas[i] - cost[i]

            total += diff
            tank += diff

            if tank < 0:
                start = i + 1
                tank = 0

        if total < 0:
            return -1

        return start

Code Explanation

We track total fuel balance:

total += diff

This tells us whether the entire circle has enough gas.

We also track the current candidate start balance:

tank += diff

This tells us whether we can still continue from the current start.

When tank becomes negative:

if tank < 0:

the current start fails.

So we try the next station:

start = i + 1
tank = 0

Resetting tank means we begin a new candidate route from i + 1.

At the end:

if total < 0:
    return -1

No start can work if total gas is smaller than total cost.

Otherwise:

return start

returns the unique valid starting station.

Testing

def run_tests():
    s = Solution()

    assert s.canCompleteCircuit(
        [1, 2, 3, 4, 5],
        [3, 4, 5, 1, 2],
    ) == 3

    assert s.canCompleteCircuit(
        [2, 3, 4],
        [3, 4, 3],
    ) == -1

    assert s.canCompleteCircuit(
        [5],
        [4],
    ) == 0

    assert s.canCompleteCircuit(
        [1],
        [2],
    ) == -1

    assert s.canCompleteCircuit(
        [3, 1, 1],
        [1, 2, 2],
    ) == 0

    assert s.canCompleteCircuit(
        [1, 2, 3, 4],
        [2, 2, 2, 2],
    ) == 1

    print("all tests passed")

run_tests()

Test meaning: