public int canCompleteCircuit(int[] gas, int[] cost) {
int pos = 1, curr = 0, total = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i]  cost[i];
curr += diff;
total += diff;
if (curr < 0) {
// use up all the gas in current run
// reset from the next one
curr = 0;
pos = i;
}
}
if (total >= 0) return pos + 1;
return 1;
}
Clean Java O(n) solution


Complex Solution:
public int canCompleteCircuit(int[] gas, int[] cost) { int tag = 0; int tank = gas[0]  cost[0]; int cur = 0; int circle = 0; while (true) { cur++; if (cur >= gas.length) { cur = 0; circle++; } if (cur == tag) { if (tank >= 0) { return tag; } else { return 1; } } if (tank < 0) { if (circle >= 1) { return 1; } else { tag = cur; tank = 0; } } tank += gas[cur]; tank = cost[cur]; } }