Skip to main content

0055 - Jump Game (Medium)

Problem Statement

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.

Return true if you can reach the last index, or false otherwise.

Example 1:

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.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.


  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Approach 1: Greedy

We can solve this backwards by tracking the furthest position we can jump, and moving it backwards if we can reach that position from the current position.

By initializing a finishfinish at nums.lengthnums.length and iterating backwards through the numbers and setting our finishfinish to ii if the current number plus ii is greater than or equal to our finish, we can find the answer if we can eventually get our finishfinish to reach 0.

Time Complexity: O(n)O(n) where nn is the length of numsnums. We only need to iterate through each number in the numsnums array once.

Space Compelxity: O(1)O(1). We only need constant space to track our finishfinish line.

Written by @ColeB2
class Solution:
def canJump(self, nums: List[int]) -> bool:
# initialize a finish line
finish = len(nums) - 1
# loop through numbers backwards
for i in range(len(nums) - 1, -1, -1):
# if we can jump past our finish line from current position:
if nums[i] + i >= finish:
# move our finish line to current position, as we know
# if we ever reach this position, we can reach the finish
finish = i
# if our finish reaches 0, we know we can successfully reach
# the finish line, if not, this will return False.
return finish == 0