Jump Game

Patrick Leaton
Published: May 11, 2021, 5:10 a.m.
Problem Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

 

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.

 

Constraints:

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

 

The description was taken from https://leetcode.com/problems/jump-game/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        flag = len(nums) - 1
        for i in range(len(nums) -1, -1, -1):
            if nums[i] + i >= flag:
                flag = i
        return flag == 0

Problem Explanation

Let's view each element as how many "distance points" we have.  If we don't want to use our entire amount of distance points to leap the entire distance from our current index, we can use a portion to hop to a more suitable position. 

Now let's think about how we can solve this question.

Instead of calculating and storing each position that leads to a good path, let's take a backward approach.

We know that the last position is ultimately where we want to jump to or past, so why don't we traverse the array backward with a flag that will let us know the last index we were able to get to the end from?

If by doing this we reach the first index of the array, then we know we can make the travel to the last position of the array.

Let's start by setting a flag marker at the last index of the array.

        flag = len(nums) - 1

 

Next, we will traverse the array backward and during each iteration, we will check if our current distance points plus our current position number can get to or past the flag. 

If so, we will move the flag to the current position.

        for i in range(len(nums) -1, -1, -1):
            if nums[i] + i >= flag:
                flag = i

 

Finally, we will return if we were able to plant the flag at the first position of the array.

        return flag == 0