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;
}
O(n) java solution, no nested loop


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

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; }
}