[LeetCode/Python] 55. Jump Game

📌 Problem

[LeetCode] 55. Jump Game

📌 Solution

Idea

Check reachability backwards

• Traverse the array backwards to check reachability
• Keep a marker idx as the current goal position
• If the current index can reach idx, move the goal to this index
• In the end, if the goal reaches index 0, it means the start can reach the end → return True

Code

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

        for i in range(n-2, -1, -1):
            if nums[i] >= idx - i:
                idx = i
            
        return idx == 0