Status: Time Limit Exceeded


  • 0
    C

    Who can tell me why I meet with this problem?
    I know that I didn't deal with the 0, but I don't think it's the problem.
    Would you please help me?

    Thanks.

    Last executed input: [25000,24999,24998,24997,24996,24995,24994,24993,24992,24991,24990,24989,24988,24987,24986,24985,24984......

    class Solution {
        public:
            int jump(int A[], int n) {
                if( n == 0 || n == 1 )
                    return 0;
                if( n ==2 || A[0] >= n-1 )
                    return 1;
                int* dp = new int[n];
                memset( dp, 0, n);
                for( int i = 0; i < n; ++i ) {
                    int maxj = A[i];
                    if( maxj + i + 1 >= n ) {
                        return dp[i] + 1 ;
                    }
                    for( int j = i + 1; j < maxj + i + 1; ++j ) {
                        if( dp[j] == 0 ) {
                            dp[j] = dp[i] + 1;
                        }
                    }
                }
                return dp[n-1];
            }
        };

  • 0
    S

    What's time complexity of your solution? Could you please elaborate thoughts?


  • 4
    M

    If I remember this test case correctly, it constantly decrements by 1 until it reaches a value of 1, which then repeats to reach the final spot, so the ending is:

    5,4,3,2,1,1,1
    

    As you can see, only the penultimate element can go further than the 2nd to last, so your loop will run on every element in the array (n repetitions). For each repetition, since the loop checks every element that can be reached (even if it doesn't write to the array) and every element reaches the penultimate element, the average length for a single repetition is (n-1)/2, or O(n). Since n*O(n) = O(n^2), that is what your time complexity is.

    There is a way to determine the number of jumps required in O(n) time, which is why you are getting the TLE.

    As a hint, you don't need to know the minimum number of jumps to reach any given point, just the minimum for the final one. Therefore, try keeping track of how far k jumps can get you, and see what the smallest k is that can reach the end.


Log in to reply
 

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