Python Programming Challenge 16: Leetcode Jump Game

Today, we have another Python programming challenge taken from Leetcode – The Leetcode jump game problem.

We’ll discuss a suggested approach for this Leetcode problem, followed by a fully explained Python solution.

Ready?

The Leetcode Jump Game problem

Let’s start with the problem first. This problem requires us to write a function that accepts a list of non-negative integers. Each element in the list represents your maximum jump length at that position.

We always start at index 0. Based on the maximum jump length at each position, your function should determine if it is possible to reach the last index in the list. If it is possible, the function returns True. Else, it returns False.

Example 1

For instance, suppose we have the list [1, 1, 0, 3].

We start at index 0, which has a value of 1. This means that from this position, we can only jump one step forward. That brings us to index 1.

From index 1, we can jump a maximum of 1 step forward again. This brings us to index 2.

From index 2, we can jump a maximum of 0 step forward. This means we’ll not be able to reach the last index as we are unable to move forward from index 2.

Hence, the function should return False.

Example 2

Next, let’s look at another example. Suppose we have the list [1, 2, 0, 3] now.

From index 0, we can jump one step forward to index 1. When we reach index 1, we can jump a maximum of 2 steps forward. If we jump 1 step forward, we’ll be stuck. However, if we jump 2 steps forward, we’ll reach the last index. Hence, the function should return True.

Suggested Approach for the Leetcode Jump Game problem

To solve this Leetcode problem, the easiest way is to start from the second last element of the list and move backwards until we reach the first element in the list.

As we iterate through the list in reverse order, we determine if each position is good or bad. A position is good if it is possible to reach the last index from that position. Else, it is bad.

Let’s consider an actual example.

Example 1

Suppose we have the list [2,3,1,1,4].

We’ll start from the second last element in the list – [2, 3, 1, 1, 4] (i.e. index 3). This element allows us to jump one step forward, which brings us to the last element. Hence, index 3 is considered a good position.

Next, we move to index 2 in the list – [2, 3, 1, 1, 4]. Once again, this element allows us to jump one step forward, which brings us to index 3. From index 3, we can move one step forward to the last element. Hence, index 2 is also considered good.

Next, we move to index 1 in the list – [2, 3, 1, 1, 4].  Once again, this position is considered good as it allows us to jump 3 steps forward. Jumping three steps forward brings us to the last element in the list.

Finally, we proceed to index 0 in the list – [2, 3, 1, 1, 4]. This element allows us to jump a maximum of 2 steps forward. If we jump one step forward, we reach the 2^nd element in the list. From there, we can jump three steps forward to reach the last element. Hence, index 0 is also considered a good position.

Once we reach index 0 in the list, we return True if it is a good position. Else, we return False.

Got it?

Example 2

Let’s consider one more example.

Suppose we have the list [0, 1, 5].

We start from the second last element (i.e. index 1). This position is good as we can move one step forward to the last element.

However, when we move to the first element (i.e. index 0), we are stuck. From index 0, we are allowed to move 0 steps forward. Hence, it is impossible for us to reach the last element in the list. Therefore, the function should return False.

Based on the suggested approach above, try solving this challenge yourself.

Suggested Leetcode Jump Game Solution in Python

The suggested solution for the Leetcode Jump Game problem in Python is shown below:

def canJump(nums):
    if len(nums) == 1:
            return True

    minStepsRequired = 0
    previousGood = len(nums)-1
    
    # work backwards and see if can reach final cell
    for i in range(len(nums)-2, -1, -1):
        minStepsRequired = previousGood - i
        if nums[i] >= minStepsRequired:
            previousGood = i

    return previousGood == 0

Here, we first define a function called canJump() that has one parameter – nums.

Inside the function, we determine if the length of nums is 1. If it is, we return True as by definition, since we start at position 0 and the list only has one element, we have successfully reached the last element in the list.

Next, we declare two variables – minStepsRequired and previousGood.

minStepsRequired stores the minimum number of steps required to reach the most recent position that is considered good.

previousGood, on the other hand, stores the index of that position.

We initialise previousGood to the index of the last element in nums as we’ll be iterating nums backwards and the last position is always considered to be a good position.

Iterating Backwards using range() function

From lines 9 to 12, we have a for loop that uses the range() function to iterate through nums.

Recall that the range(a, b, c) function returns a sequence of numbers starting from a and ending one number before b.

c specifies the incrementation to use.

In our suggested solution, a equals len(nums)-2, b equals -1 and c equals -1.

This means we want the range() function to start from len(nums)-2 and keep decreasing by 1 until we reach one number before b (i.e. one number before -1, which is 0).

This results in the for loop iterating from the second last element in the list to the first element.

Inside the for loop

Inside the for loop, we calculate the minimum number of steps required to reach the most recent good position (on line 10).

Suppose nums = [1, 1, 2, 4, 1].

The first time the for loop runs, we’ll be at the second last element in nums (i.e. at index 3).

previousGood stores the index of the last element in nums, which is 4.

minStepsRequired will then be previousGood - i (where i stores the current index) = 4 – 3 = 1.

This means that at index 3, we only need to jump one step to reach the most recent position that is considered good.

On line 11, we check if it is possible to jump one step from index 3. Since nums[3] is 4 (which is greater than or equal to 1), it is possible. Hence, index 3 is considered to be a good position.

Therefore, we update the value of previousGood to 3 (on line 12).

At each step as we iterate through nums, we keep checking if it is possible to reach the position indicated by previousGood from the current index. If it is, we update the value of previousGood to the current index.

For instance, when i equals 2 (i.e. at index 2), previousGood is 3.

We need to check if it is possible to jump from index 2 to index 3. If it is possible to reach index 3 from index 2, we know that it is possible to reach the last element in nums. This is because from index 3, we can jump to index 4, which is the last element.

Since we only need to jump one step from index 2 to index 3 (as calculated by the formula on line 10), and nums[2] is 2, it is possible.

Hence, index 2 is considered to be a good position and we update the value of previousGood to 2.

We keep doing that until we finish iterating through all the elements in nums.

After the for loop

After iterating through all the elements in nums, if the final value of previousGood is 0, we know that position 0 is a good position. This means it is possible to reach the last element from index 0.

If that’s the case, we return True.

We do that by returning the result of the condition previousGood == 0 on line 14. If previousGood == 0 returns True, we return True. Else, we return False.

With that, the function is complete.