Why so sensitive?


  • 3
    S

    After using recursive method, it says time exceeds, then I know I should try DP.
    Please take a look at the two codes below, they both use DP, and the only difference between them is just a line in the for( ; ; ) part. Why so sensitive??? Could anyone tell me why one of them is accepted but the other is rejected? Is the accepted one better than the other one generally, or just in terms of the certain test data?

    public boolean canJump(int[] A) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(A.length==0)
        return false;
        if(A.length==1)
        return true;
        boolean[] flag = new boolean[A.length];
        flag[A.length-1] = true;
        for(int i=A.length-2; i>=0; i--) {
            for(int j=i+1; j<A.length&&j<=i+A[i]; j++) {
                if(flag[j]==true) {
                    flag[i] = true;
                    break;
                }
            }
        }
        return flag[0];
    }
    public boolean canJump(int[] A) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(A.length==0)
        return false;
        if(A.length==1)
        return true;
        boolean[] flag = new boolean[A.length];
        flag[A.length-1] = true;
        for(int i=A.length-2; i>=0; i--) {
            for(int j=Math.min(A.length-1,i+A[i]); j>i; j--) {
                if(flag[j]==true) {
                    flag[i] = true;
                    break;
                }
            }
        }
        return flag[0];
    }

  • 0
    C

    I think there is no significant difference between these two methods. Just some specific test cases take different time.


  • 8
    L

    Indeed, you seem to be exactly where OJ put the TLE cut-off.
    OJ always uses the same data set, but the running time of your algorithm varies for different submissions. There are many reasons for that. It could be that the server is overloaded, it could be that the garbage collector decides to run, or some pagination in memory…

    (Side note: time is tricky measure of complexity in computer science, because it not well define, depends of your hardware, other running software, etc. whereas counting only certain operations – such as the number of access of an array – is much more practical.)

    The main problem here is that your algorithm works is O(n^2) in worse case and use O(n) memory.
    There exists a linear time and constant space algorithm for this problem.

    If you are not convinced that your algorithm runs in O(n^2), think about it with that particular input: [6,5,4,3,2,1,1,0,0]. One of the tests that OJ does is exactly this, but instead of starting at 6, it starts at 25,000. (and 25,000^2 = 625 millions…)


  • 0
    S

    Thank you for your thorough answer.


  • 1
    A

    Actually, This problem can be solved with O(n) time complexity


Log in to reply
 

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