MediumNo. 0055

Jump Game — LeetCode 55 Python Solution

Pattern
Greedy
Topics
Greedy, Array, Dynamic Programming
Reading time
2 min

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

PythonSolution
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

Time
O(n)where n is the length of the array
Space · auxiliary
O(1)

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

Related problems
No.ProblemDifficulty
0045Jump Game IIMedium
1340Jump Game VHard
1696Jump Game VIMedium
1306Jump Game IIIMedium
1345Jump Game IVHard
1871Jump Game VIIMedium

Frequently asked questions

How hard is LeetCode 55. Jump Game?

LeetCode 55. Jump Game is rated Medium on LeetCode.

What is the time complexity of LeetCode 55. Jump Game?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 55. Jump Game?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 55. Jump Game cover?

LeetCode 55. Jump Game is tagged Greedy, Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.