Getting TLE on the test case with {25000........24000}


  • 0
    P
    int jump(int a[], int n) {
            if (n==1) return 0;
            
            vector<int> reach(n,INT_MAX);
            reach[0] = 0;
            //reach[n-1] = ;
            for (int i = 0; i < n; ++i) {
                for (int j = a[i]; j > 0; --j) {
                    if (j+i < n) {
                        reach[j+i] = min(reach[j+i], i);
                    } else {
                        reach[n-1] = min(reach[n-1],i);
                        //break;
                    }
                }
            }
            
            // trace back;
            int steps = 0;
            int i = n-1;
            while(reach[i] > 0) {
                steps++;
                i = i-reach[i];
            }
            return steps;
        }

Log in to reply
 

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