Instantly share code, notes, and snippets.

# jingz8804/GasStation.java Last active Aug 29, 2015

#leetcode
 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; } }
to join this conversation on GitHub. Already have an account? Sign in to comment