# O(n) java solution, no nested loop

• ``````public int canCompleteCircuit(int[] gas, int[] cost) {
int i = 0;
int deficit = 0;

for(; i < gas.length; i++){
int extra = gas[i] - cost[i];
if(extra >= 0)
break;
else
deficit -= extra;
}

if(i == gas.length)
return -1;

int tank = 0;
int start = i;
for(; i < gas.length; i++)
{
tank += gas[i] - cost[i];
if(tank < 0){
start = i + 1;
tank = 0;
}
}

if(start == gas.length || tank < deficit)
return -1;

return start;
}``````

• Let's say gas is {1,1,1}, cost is {1,100,1}. Apparently there's no solution, but your code will return 2. It does get AC though. Is it lacking test cases or am I misunderstanding the question?

• yes, you are right, there is no enough test cases, you can see my solution, that is correct.
https://leetcode.com/discuss/33985/my-o-n-java-solution

• You are right, my previous solution was incorrect. This solution should work:

public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {

``````    int remaining = 0;
int deficit = 0;
int start = 0;

for(int i = 0; i < gas.length; i++){
int extra = gas[i] - cost[i];
remaining += extra;

if(remaining < 0){
deficit -= remaining;
remaining = 0;
start = i + 1;
}
}

if(start == gas.length || remaining < deficit)
return -1;

return start;
}
``````

}

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