Gas Station Problem

You have gas stations arranged in a circle. Each station gives you some gas, and it costs gas to reach the next station. You want to find where to start so you can complete the whole loop.

Your car starts with no gas. If you can’t make it around, return -1.

Here are the key insights:

The total gas must be greater than or equal to the total cost. Otherwise the trip is impossible.

If you can’t make it from station A to station B, then any station between A and B also won’t work as a starting point. This saves us work.

Here’s the code:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total=0, sum=0, start=0;
    for(int i=0;i<gas.size();++i) {
        total += gas[i]-cost[i];
        sum += gas[i]-cost[i];
        if (sum < 0) {
            start = i+1;
            sum=0;
        }
    }
    return (total<0) ? -1 : start;
}

The algorithm works like this:

• total tracks the overall gas balance across all stations
• sum tracks the current trip’s balance
• start holds our potential starting point

When sum goes negative, we reset our starting point to the next station. We clear sum because we can’t carry negative gas forward.

At the end, if total is negative, the whole trip is impossible. Otherwise, start tells us where to begin.

This runs in O(n) time and O(1) space. The insight about skipping ranges saves us from checking every possible starting point individually.

#greedy