You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i j] where:

0 <= j <= nums[i] and i j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2:

Input: nums = [2,3,0,1,4] Output: 2

My solution:

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        j = len(nums)-1
        res = []
        while j >= 0:
            cursor = j

            valid_j = j # this variable will hold the best value of j to be set
            while cursor >= 0:
                if nums[cursor]   cursor >= j:
                    valid_j = cursor
                cursor-=1
            
            res.append(valid_j)
            
            j = valid_j

        return len(res)

Either of the while loop doesn't terminate and I am unable to figure out why. Time limit exceeded error. Please help by explaining the error.

Thanks!

CodePudding user response：

Seems like valid_j is not being incremented.

CodePudding user response：

Your while condition is wrong. It will always be true since j is never going to become negative.

The meaning of j in your algorithm is the index that must be jumped to from some earlier index. But index 0 must never be jumped to, since we already achieved that index by starting there.

To fix this, the while condition should be changed to j > 0.

It should be noted that this is not a very efficient solution, as cursor is repeatedly reading the same values of the list, giving this algorithm a worst time complexity of O(