Gas Station

How it works

We want to find a gas station index from which we can complete the entire circular route without the gas tank ever going negative.

First, notice an important fact:

• If the total gas available is less than the total cost required, then it is impossible to complete the circuit from any station.

If the total gas is sufficient, then at least one valid starting station exists. Under this problem's guarantee, there will be at most one valid answer.

The greedy idea is to scan the stations from left to right while keeping track of the current tank balance.

• If at some index the tank becomes negative, it means we cannot start from any station between the previous start and this index, because they would all run out of gas at the same point.
• So we reset the tank and try the next station as a new starting point.

Steps

1. Check if the total gas is less than the total cost:
   • If sum(gas) < sum(cost), return -1 immediately.
2. Initialize:
   • total = 0 to track the current gas balance.
   • res = 0 to store the candidate starting index.
3. Iterate through all stations from index 0 to n - 1.
4. At each station i:
   • Add the net gas change:
     • total += gas[i] - cost[i]
5. If total becomes negative:
   • The current starting point cannot work.
   • Reset total = 0.
   • Set the next station as the new candidate start: res = i + 1.
6. After finishing the loop:
   • Return res as the valid starting station.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Check Total Gas vs Total Cost First

The greedy solution assumes a valid starting point exists if total gas is sufficient. However, skipping this global check can cause returning an invalid index when no solution exists. Always verify sum(gas) >= sum(cost) before applying the greedy logic, or the algorithm may return a false positive starting index.

Resetting to an Invalid Starting Index

When the running tank goes negative at index i, the new candidate start should be i + 1. A common mistake is setting it to i, which is guaranteed to fail since we just proved the journey fails at that point. Additionally, when i + 1 equals n, there's no valid start, but this is handled by the total gas check.

Not Understanding Why Failed Stations Can Be Skipped

The greedy approach skips all stations between the previous start and the failing point. This works because if we cannot reach station j starting from station i, we also cannot reach j starting from any station between i and j. Those intermediate stations have strictly less accumulated gas when reaching j. Understanding this principle is key to trusting the linear-time solution.

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        total = 0
        res = 0
        for i in range(len(gas)):
            total += (gas[i] - cost[i])

            if total < 0:
                total = 0
                res = i + 1

        return res

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if (accumulate(gas.begin(), gas.end(), 0) <
            accumulate(cost.begin(), cost.end(), 0)) {
            return -1;
        }

        int total = 0;
        int res = 0;
        for (int i = 0; i < gas.size(); i++) {
            total += (gas[i] - cost[i]);

            if (total < 0) {
                total = 0;
                res = i + 1;
            }
        }

        return res;
    }
};