# Share my idea prograss from brute force to greedy stragedy

• ``````//brute force : time limit exceeded
public int canCompleteCircuit(int[] gas, int[] cost) {
int ret = -1;
for (int i = 0; i < gas.length; i++) {
int sum = 0, count = 1;
for (int start = i; count <= gas.length; start++){
sum += gas[start % gas.length] - cost[start % gas.length];
count++;
if(sum < 0) break;
}
if(sum >= 0) return i;
}
return ret;
}
// pruning algorithm : 1ms
// if sum of gas station from i to j is negative, then there are no start point from i to j.
public int canCompleteCircuit(int[] gas, int[] cost) {
int ret = -1;
for (int i = 0; i < gas.length; ) {
int sum = 0, count = 1, start = i;
for ( ; count <= gas.length; start++){
sum += gas[start % gas.length] - cost[start % gas.length];
count++;
if(sum < 0) break;
}
if(sum >= 0) return i;
else i = start + 1;
}
return ret;
}
// greed strategy : 0ms
// if sum of all of gas[i] - cost[i] is non-negative, there are gas station where can be start
// if sum of gas station from i to j is negative, then there are no start point from i to j
// we choose the gas station that first point of sum of subrange is non-negative and other subrange is negative.
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0, localSum = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
localSum += gas[i] - cost[i];
if(localSum < 0){
sum += localSum;
localSum = 0;
start = i + 1;
}
}
return sum + localSum < 0 ? -1 : start;
}``````

• please forget my poorly english

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