Super simple solution in Java, runs within 200ms

• ``````public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int l = 0;
int r = 1 % n;
int sum = gas[l] - cost[l];
while(l < n && l != r) {
if (sum < 0) {
sum -= gas[l] - cost[l];
l++;
if (l != r) continue;
}
sum += gas[r] - cost[r];
r = (r + 1) % n;
}

if (l == n || sum < 0) return -1;
return l;
}
}
``````

The basic idea is that we put two pointer `l` and `r` on the array and maintains the sum of `gas[i] - cost[i]` from `l` to `r` (in a recurring way for `r` but not `l`), once we found an `l` that enables `r` to travel to the same position of `l` without `sum < 0` at any single step, we know `l` now is the solution of the problem.

Otherwise, If at last `l` travels to `n`, we have already tried every index and no one can make `r` travels back, there is no solution for this problem. Same result when the sum at last is negative.

`l` moves at most `n` steps, `r` moves at most `2 * n` times, so the time complexity is `O(n)`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.