# Really Weird TLE...Need help.

• Following is my AC(TLE) code, if I change one line from

``````j = (j == gas.length - 1)? 0 : j + 1;
``````

to

``````j = (j == len - 1)? 0 : j + 1;
``````

it will get TLE, but I think if I use cached variable it would be faster, isn't it?
Confused why the TLE occurs between this small change.

``````public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
if (len == 0) {
return 0;
}

// iterate all indexes, starting from each index, see whether
// we can go for a length of the array.
for (int i = 0; i < len; i++) {
int station = len;
int tank = gas[i];
int j = i;

while (station > 0) {
if (tank - cost[j] < 0) {
break;
}
tank -= cost[j];
// OMG, the following will get TLE:
//  j = (j == len - 1)? 0 : j + 1;
j = (j == gas.length - 1)? 0 : j + 1;
tank += gas[j];
station--;
}

if (station == 0) {
return i;
}

}

return -1;
}
``````

}

• I think the key thing of TLE is that this algorithm is O(n^2) complexity, the key point here is that from index i, if you go forward to i+1, i + 2, .. j and find that the inner loop quits because of the condition tank - cost[j] < 0, you can safely move i to j + 1 since any index from i + 1 to j will match the tank - cost[j] <0 condition. Then after a scan of i staring from 0, you could find the index that matches the condition station == 0, which reveals the correct answer, or i goes beyond n - 1 and the function should return -1.

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