In a single player jump game, the player starts at one end of a series of squares and aims to reach the last square.

At each turn, the player can take up to $s$ steps toward the last square, where $s$ is the value of the current square.

For example, if the value of the current square is $3$, the player can take either $3$ steps, $2$ steps, or $1$ steps in the direction of the last square. The player cannot move in the opposite direction, away from the last square.

You’ve been provided with the nums integer array, representing the series of squares.

You’re initially positioned at the first index of the array. Find the minimum number of jumps needed to reach the last index of the array.

You may assume that you can always reach the last index.

Constraints

• $1 \leq$ nums.length $\leq 10^3$

• $0\leq$ nums[i] $\leq 10^3$

We’ll solve this problem using a greedy approach. At each step, we choose the jump that allows us to reach the farthest point. The objective is to minimize the number of jumps required to reach the end of the array. This strategy is considered greedy because it selects the best possible move at each step without considering the impact on future jumps. By always jumping as far as possible, we cover more distance and use fewer jumps to reach the end.

To find the minimum number of jumps needed to reach the end of the array, keep track of how far you can go with the current number of jumps. As you progress through the array, update this maximum reach based on your current position. When you reach the limit of your current jump range, increase your jump count and adjust the range to the farthest position you can reach with the next jump. Continue this process until you reach or exceed the end of the array.

The steps of the algorithm are given below:

1. Initialize three variables, all set to 0.

   1. jumps: This variable tracks the minimum number of jumps required to reach the end of the array and will be returned as the final output.

   2. current_jump_boundary: This represents the maximum index we can reach with the current number of jumps. It acts as the boundary of how far we can go before making another jump.

   3. farthest_jump_index: This tracks the farthest index we can reach from the current position by considering all possible jumps within the current jump’s range.

2. Iterate through the nums array and perform the following steps:

   1. Update farthest_jump_index: For each index i, calculate i + nums[i], which represents the farthest index we can reach from i. Update farthest_jump_index to be the maximum of its current value and i + nums[i].

   2. Check if a new jump is needed: If i equals current_jump_boundary, it means we’ve reached the limit of the current jump. Increment jumps by 1, and update current_jump_boundary to farthest_jump_index to set up for the next jump.

3. After iterating through the array, jumps will contain the minimum number of jumps needed to reach the end. Return this value as the output.

Let’s look at the following illustration to get a better understanding of the solution: