Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment