## Algorithm

Problem Name: 45. Jump Game II

You are given a 0-indexed array of integers `nums` of length `n`. You are initially positioned at `nums[0]`.

Each element `nums[i]` represents the maximum length of a forward jump from index `i`. In other words, if you are at `nums[i]`, you can jump to any `nums[i + j]` where:

• `0 <= j <= nums[i]` and
• `i + j < n`

Return the minimum number of jumps to reach `nums[n - 1]`. The test cases are generated such that you can reach `nums[n - 1]`.

Example 1:

```Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
```

Example 2:

```Input: nums = [2,3,0,1,4]
Output: 2
```

Constraints:

• `1 <= nums.length <= 104`
• `0 <= nums[i] <= 1000`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int jump(vector& nums) {
int minJump = nums.size();
DFS(nums, 0, 0, minJump);
return minJump;
}

void DFS(vector& nums, int pos, int jump, int& minJump){
if(pos == nums.size() - 1){
minJump = min(minJump, jump);
return;
}
int next = pos + 1, maxlen = 1 + nums[pos + 1];
for(int i = 1; i <= nums[pos] && pos + i < nums.size(); i++)
if(i + nums[pos + i] > maxlen || pos + i == nums.size() - 1) next = pos + i, maxlen = i + nums[next];
DFS(nums, next, jump + 1, minJump);
}
};

``````
Copy The Code &

Input

cmd
nums = [2,3,1,1,4]

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const jump = function(nums) {
if (nums.length <= 1) return 0;
let curMax = 0; // to mark the last element in a level
let level = 0, i = 0;
while (i <= curMax) {
let furthest = curMax; // to mark the last element in the next level
for (; i <= curMax; i++) {
furthest = Math.max(furthest, nums[i] + i);
if (furthest >= nums.length - 1) return level + 1;
}
level++;
curMax = furthest;
}
return -1; // if i < curMax, i can't move forward anymore (the last element in the array can't be reached)
};
``````
Copy The Code &

Input

cmd
nums = [2,3,0,1,4]

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def jump(self, nums):
last = cur = jump = i = 0
while cur < len(nums) - 1:
while i <= last:
if i + nums[i] > cur: cur = i + nums[i]
i += 1
last = cur
jump += 1
return jump
``````
Copy The Code &

Input

cmd
nums = [2,3,1,1,4]

Output

cmd
2

### #4 Code Example with C# Programming

```Code - C# Programming```

``````namespace LeetCode
{
public class _045_JumpGame2
{
public int Jump(int[] nums)
{
int maxRight = 0, currentRight = 0, count = 0;

for (int i = 0; i < nums.Length; i++)
{
if (i > maxRight) { return 0; }
if (i > currentRight)
{
count++;
currentRight = maxRight;

}
if (i + nums[i] > maxRight) { maxRight = i + nums[i]; }
}

return count;
}
}
}

``````
Copy The Code &

Input

cmd
nums = [2,3,0,1,4]

Output

cmd
2