Jump Game I

Try to solve the Jump Game I problem.

We'll cover the following

Statement#

In a single-player jump game, the player starts at one end of a series of squares, with the goal of reaching the last square.

At each turn, the player can take up to ss steps towards the last square, where ss is the value of the current square.

For example, if the value of the current square is 33, the player can take either 33 steps, or 22 steps, or 11 step in the direction of the last square. The player cannot move in the opposite direction, that is, away from the last square.

You have been tasked with writing a function to validate whether a player can win a given game or not.

You’ve been provided with the nums integer array, representing the series of squares. The player starts at the first index and, following the rules of the game, tries to reach the last index.

If the player can reach the last index, your function returns TRUE; otherwise, it returns FALSE.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3
  • 0≤0 \leq nums[i] ≤103\leq 10^3

Examples#

Created with Fabric.js 3.6.6 Output TRUE nums 2 3 1 1 4 Output Input Sample example 1 The value at every index representsthe maximum number of jumps you cantake from that point.

1 of 5

Created with Fabric.js 3.6.6 Output TRUE Output nums 2 3 1 1 4 Input Sample example 1 You start from the first index. As the valuehere is 2, you can make a jump of up to 2 indexes from here.

2 of 5

Created with Fabric.js 3.6.6 Output TRUE Output nums 2 3 1 1 4 Input Sample example 1 Suppose you choose to move just 1 index to the right.

3 of 5

Created with Fabric.js 3.6.6 Output TRUE Output nums 2 3 1 1 4 Input Sample example 1 You can make up to 3 jumps from here. In this case, the farthest element you can reach (with 3 jumps), is the last element.As the last index is reachable, we return TRUE.

4 of 5

Created with Fabric.js 3.6.6 Output Input Sample example 2 Output FALSE You can't reach the end of the array with the followingarrangement, because the farthest you can travel fromthe first three elements is to the second-last element. Its value is 0, which indicates that you can't jump any further from this point. nums 3 2 1 0 4

5 of 5

Understand the problem#

Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:

Jump Game I

1

Can you reach the end of [1, 2, 3, 4, 5] if you start from the very first element?

A)

Yes

B)

No

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct order.

Set the last element in the array as your initial target.

Traverse the array from the end to the first element in the array.

If the current index is reachable from any preceding index, based on the value at that index, make that index the new target.

If you reach the first index of the array without finding any index from which the current target is reachable, return FALSE.

Else, if you are able to move each current target backward all the way to the first index of the array, you’ve found a path from the start to the end of the array. Return TRUE.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
Input #1
%0 node_01 2 node_11 3 node_21 1 node_31 1 node_41 9
Visualization for Input #1
Jump Game I

Greedy Techniques: Introduction

Solution: Jump Game I