[LeetCode] Gas Station

Problem Statement (link):

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Analysis:
Brute force solution is trying out every possible start index, if the cumulative gas is negative at some point, it implies the start index we chose is not a valid solution, we will then move to next index to check. This algorithm could be implemented with two for loops and yield a O(N^2) time complexity.

To figure out a more efficient solution, we need to think about the characteristics of this problem. We notice that:
- If starts at index i, the car has to stop at station j if the left gas in the tank plus gas[j] is smaller than cost[j]. The left gas is calculated by summing up gas[i : j] minus cost[i : j];
- Further, if a car stops at station j, then any station between i and j could not be a starting station. This is crucial to lower time complexity. Consider station k, where i<k<j, as the car doesn't stop until station j, then the gas-cost sum from i to k must be positive; also, as the car stop at station j, then the gas-cost sum from i to j must be negative, this implies that the gas-cost sum from k to j must be negative, thus, k could not be a starting point.

With this understood, we start at any station i, and accumulate gas-cost. Once we find the accumulation is negative at station j, we change the starting station to the next station j+1, rather than i+1 in the brute force algorithm. The new algorithm has O(N) complexity. If the accumulative sum of all gas-cost is negative, we return -1 as there is no possible solution; otherwise, we return the start station index.

Code:

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int st=0, left=0, sum=0; // left-gas left in the tank
        for (int i=0; i<gas.size(); i++) {
            left+=gas[i]-cost[i];
            sum+=gas[i]-cost[i];
            if (sum<0) {
                sum=0;
                st=i+1;
            }
        }
        return left<0 ? -1:st;
    }
};