Demonstrate the detailed flow|process of my thinking


  • 6
    M
    one example:
    index      0  1  2  3  4  5  6  7  8  9  10  11
    value      5  9  3  2  1  0  2  3  3  1  0   0
    farthest   5  10 10 10 10 10 10 10 11 11 11  11
        
        my thought -- scan from right to left.
        
            -- to reach index 11, we have to first reach (try best to jump forward)
                -- index 0, 0+5=5, no
                -- index 1, 1+9=10, no
                -- index 2, 2+3=5, no
                -- index 3, 3+2=5, no
                -- index 4, 4+1=5, no
                -- index 5, 5+0=5, no
                -- index 6, 6+2=8, no
                -- index 7, 7+3=10, no
                -- index 8, 8+3=11, yes!
                thus we have to first reach index 8.
            -- to reach index 8, we have to first reach (try best to jump forward)
                -- index 0, 0+5=5, no
                -- index 1, 1+9=10, yes
                thus we have to first reach index 1.
            -- to reach index 1, we have to first reach (try best to jump forward)
                -- index 0, 0+5=5, yes
                thus we have to first reach index 0.
            
            therefore, 3 steps in total.
            
        one issue i thought about.
            -- when scanning from left to right to search for the "viable" index, we take the first "viable" index.
               what if this first "viable" index is not reachable?
               
               for example:
               index  0  1  2  3  4  5  6  7  8  9  10  11
               value  1  6  5  4  3  2  1  3  3  1  1   0
               
               scanned from left to right, the first "viable" index is 8, the second "viable" index is 10.
               what if we cannot reach index 8 but we can reach index 10?
                    -- silly question, lol
               will it take more steps to choose index 8 than 10?
                    -- 8-->11 and 10-->11 both take 1 step
                    -- will it take more steps to reach index 8 than 10?
                        -- the answer is **NO**.
                           if reaching index 10 takes **n** steps, we can definitely reach index 8 in **<=n** steps.
               
               therefore we have no problem to choose the first "viable" index.
               such is the correctness of the algorithm.

  • 3
    M

    this is my code.

    public int jump(int[] nums) {
            int minStep = 0;
            int p = nums.length-1;
            while (p>0) {
                for (int i=0; i<p; ++i) { // find the first "viable" index
                    if (i+nums[i]>=p) {
                        p = i;
                        minStep += 1;
                        break;
                    }
                }
            }
            return minStep;
        }

  • 0
    K

    it got TLE...


  • 0
    M

    i tried again 1 minute ago, still can be accepted...?


  • 0
    M

    may be you just forgot the "break" in the for loop, that was why i got tle for the first time.


  • 0
    X

    If the last point is not reachable at all, it will get infinite loop. For example: {1, 3, 0, 0, 0, 0, 6, 7}


  • 0
    T
    This post is deleted!

  • 1
    T

    Thank you for your share. If the test case is [1,1,1,1,1,1,1], the time complexity should be O(n*n), which will cause TLE.


  • 0
    M
    This post is deleted!

  • 0
    M

    yes you are right ( though it says "you can assume the last point is always reachable" in the problem statement ), i should learn the right way from others, i guess... many thanks!


Log in to reply
 

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