#leetcode

GasStation.java

public class GasStation{
    public int canCompleteCircuit(int[] gas, int[] cost){
        // first check special cases
        if(gas == null || cost == null) return -1;
        if(gas.length != cost.length) return -1;
        
        // get the number of the gas stations
        int N = gas.length;
        
        int leftAmount = 0; // the amount of gas left in the tank when we are at station i
        
        int i = 0; // starting index
        int j = i; // how far we can get
        
        while(i < N){
            j = i % N;
            leftAmount = 0;
            while(leftAmount + gas[j % N] >=  cost[j % N]){ // j might be greater than N. Take mod to avoid array index overflow
                leftAmount = leftAmount + gas[j % N] -  cost[j % N]; // do not forget updating the left gas amount
                j++; // move from j to j + 1
                if(j % N == i) return i; // if we have reached station i, return i
            }
            // the next station that we should check is j + 1 (it should be (j + 1) % N)
            // we don't take the mod here because we need to cover the following case:
            //      0
            //   7     1
            // 6         2
            //   5     3
            //     4
            // Suppose we can go from station 3 and circle around to station 1 at most.
            // if we take the mod here, i becomes 2 we are stuck in the loop forever.
            // Also, the only reason that we are checking station 3 is that station 2 cannot even get to station 3.
            // So if we meet any case that (j + 1) >= N and (j + 1) % N is less than the initial starting point i, we should
            // stop the checking. In fact, j + 1>= N would be just enough. If (j + 1) % N >= i, it would be detected by the if 
            // statement in the inner while loop.
            i = j + 1; 
        }
        return -1;
    }
}