Understanding the Problem

There is a list of numbers as nums. Each number has the value from 0 to 10^5. The program starts with the first index, which is nums[0]. Every value of the list nums indicates that it can help jumping to the next indexes within the range of the value. For instance, if the list is nums = [3, 1, 0, 2, 1], starting from nums[0] the value is 3. Then the maximum distance it can reach is nums[3], and also it can reach nums[2], nums[1] as the value 3 is the range of the jumping.

When the jumping reaches the last index of the list or exceeds the length of the list, it returns True, otherwise returns False.

Approach

The instruction and explanation on LeetCode was lack of information and did not understand at once, thus I had to look into the comments of the problem. The commends were also complaining about how the instruction was unclear and other comments were helping those who think the information was confusing as well.

So, I started with reducing each value by 1 whenever the index meets the nums[i] == 0, but it was not a good idea as I had to fight with all bunch of if cases and exceptions. Half way through, I realised it was not a good idea to deduct the value from the list, and I had to find a new way of solving the problem.

I was struggling for many hours thinking that this would be ridiculous to spend more time on this. I ended up in ChatGPT to ask what this problem was about. Greedy algorithm was the idea though.

Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True

        check_point = 0

        for i, jump in enumerate(nums):
            if i > check_point: # it cannot jump further
                return False

            check_point = max(check_point, i + jump)
            if check_point >= len(nums)-1:
                return True

It was only necessary to focus on the maximum jumps from each element. It is how it works.

1. Iterate in for loop with index i and value jump

2. If the i is greater than check_point, it means it cannot jump any further, so return False

3. check_point is renewed on every step of the iteration. It has to compare with the current check_point value and i + jump value. Current index and the value indicates the maximum jump it can reach from the current position, but if the check_point was further it is useless to have that value thus discard.

4. Check if check_point can reach the last index of the list or it exceeds it. If so, return True

Reflection

It indeed was simple with the greedy algorithm. I only had to think about the maximum jump because it also covers the range of the current value as well. Other people though, they seem genius with the solution of the problem. They did it with for loop and 2-3 if conditions to solve the problem(you may see it on LeetCode solution tab).