# Ac solution code

• The basic idea is checking the remaining gas after reaching each gas station by plusing (gas[i] - cost[i]).

Greedy solution doesn't verify the remaining circular gas stations after n-1, because if total >= 0, then total(gas - cost) >= 0, which means the remaining trip after n-1 should have enough gas.That's the critical support for this one pass solution.

Solution1. Greedy - Runtime = O(n)

``````public int canCompleteCircuit(int[] gas, int[] cost) {
int index = 0, sum = 0, total = 0;
for (int i = 0; i < gas.length; i++) {
int cur = gas[i] - cost[i];

sum += cur;
if (sum < 0) {// if sum < 0, index can only start from i + 1
index = i + 1;
sum = 0;
}
total += cur;
}
}
``````

Solution2. Brute force(TLE Error) - Runtime = O(n^2)

``````public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < gas.length; i++) {
int remaining = 0;
for (int j = i; j < i + n; j++) {
remaining += gas[j % n];
remaining -= cost[j % n];
if (remaining < 0)
return -1;
}
return i;
}
return -1;
}``````

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