Really Weird TLE...Need help.


  • 0
    S

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

    }


  • 1
    J

    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.


Log in to reply
 

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