Jump Game — LeetCode 55 Python Solution

The problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Example

Input

nums = [2,3,1,1,4]

Output

true

Explanation

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Python solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        mx = 0
        for i, x in enumerate(nums):
            if mx < i:
                return False
            mx = max(mx, i + x)
        return True

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 55. Jump Game is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems