# LeetCode 134: Gas Station

## Problem Restatement

There are `n` gas stations arranged in a circle.

At station `i`:

| Array | Meaning |
|---|---|
| `gas[i]` | Amount of gas we can fill at station `i` |
| `cost[i]` | Gas needed to travel from station `i` to station `i + 1` |

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:

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

Output:

```python
3
```

Start at station `3`.

Walk through:

| Station | Fill | Cost | Tank after travel |
|---:|---:|---:|---:|
| `3` | `4` | `1` | `3` |
| `4` | `5` | `2` | `6` |
| `0` | `1` | `3` | `4` |
| `1` | `2` | `4` | `2` |
| `2` | `3` | `5` | `0` |

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

Example 2:

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

Output:

```python
-1
```

The total gas is:

```python
2 + 3 + 4 = 9
```

The total cost is:

```python
3 + 4 + 3 = 10
```

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | `gas: list[int]`, `cost: list[int]` |
| Output | Starting station index, or `-1` |
| Route | Circular |
| Tank | Starts empty, unlimited capacity |
| Guarantee | At most one valid answer exists |

Function shape:

```python
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:

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

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

That means:

```python
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:

```python
total = 0
tank = 0
start = 0
```

Then scan each station `i` from left to right.

At each station:

```python
diff = gas[i] - cost[i]
```

Add `diff` to both `total` and `tank`.

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

So:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the arrays once |
| Space | `O(1)` | Only a few integer variables are used |

## Implementation

```python
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:

```python
total += diff
```

This tells us whether the entire circle has enough gas.

We also track the current candidate start balance:

```python
tank += diff
```

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

When `tank` becomes negative:

```python
if tank < 0:
```

the current start fails.

So we try the next station:

```python
start = i + 1
tank = 0
```

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

At the end:

```python
if total < 0:
    return -1
```

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

Otherwise:

```python
return start
```

returns the unique valid starting station.

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Valid start is in the middle |
| Total gas too small | Impossible case |
| One station, enough gas | Single valid station |
| One station, not enough gas | Single invalid station |
| Start at index `0` | Valid answer can be first station |
| Reset needed before answer | Confirms greedy restart logic |