Jump Game

Problem Id: 55 Difficulty: Medium Tag: Array Tag: Greedy


Intuition

This problem could be solved by greedy. We could maintain a variable max_reachable. And then go through nodes one by one. Once a node's index is greater than max_reachable, it means we have got to the maximum node we could reach.

Solution


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable = 0
        for i, num in enumerate(nums):
            if i > reachable:
                return False
            elif i == len(nums) - 1:
                return True
            reachable = max(reachable, i + num)