# [LeetCode] Top Interview 150 Problems Solving # 55 Jump Game

# **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**

```python
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).