> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/greedy/medium/45.-jump-game-ii.md).

# 45. Jump Game II

## Problem Statement

<br>

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]`.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [2,3,1,1,4]
</strong><strong>Output: 2
</strong><strong>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.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,3,0,1,4]
</strong><strong>Output: 2
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 1000`
* It's guaranteed that you can reach `nums[n - 1]`.

## Intuition

```
Approach: DP takes n2

But greedy take O(N)
Intuition is that,

We Do like a BFS kind of thing,
We maintain a max jump and if er cross that, we incr jumps

2 3 1 4 5
_ , , | |

From 2 we can in 1 jump reach till 2 index
After that till 5 we can reach in 2 steps
```

### Links

<https://leetcode.com/problems/jump-game-ii/description/>

### Video Links

<https://www.youtube.com/watch?v=dJ7sWiOoK7g&ab_channel=NeetCode>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int jump(vector<int>& arr) {
        int farthest=0;    
        int jumps=0;         
        int current=0;  

        for(int i = 0; i < arr.size()-1; i++) {
            farthest= max(farthest,arr[i]+i);

            if(i==current){
                jumps++;
                current=farthest;
            }

        }
        return jumps; 
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###