Interesting Question: first think of backtrack or dp but finally Got it!


  • 0

    Firstly, I tried using backtrack with dp algorithm, but it gives me TLE badly.
    Then I revised my algorithm not depending on the value of nums[i], but still TLE.
    Then I thought of using PriorityQueue to keep the minIdx can reach the end, then I suddenly realise no need PriorityQueue, just maintain a minIdx will do.

    The basic idea is to start from back, if for idx i can reach the end, just set the minIdx to it, the crucial observation is that, for some idx i, if minIdx can be reached from i, i can definitely reach end, if minIdx cannot be reached from i, then i cannot reach end, just continue verify i-1, and so on.

    public boolean canJump(int[] nums) {
        if(nums.length==0)
            return false;
        int idx = nums.length-1;
        for(int i=nums.length-2; i>=0; i--)
            if(idx-i<=nums[i])
                idx = i;
        return idx==0;
    }

Log in to reply
 

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