Solution: Jump Game II
Tags: algorithms, javascript, java, python
Published: 2021-05-05 08:56:53

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/jump-game-ii/discuss/1192396).*

---

#### [Leetcode Problem #45 (*Medium*): Jump Game II](https://leetcode.com/problems/jump-game-ii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an array of non-negative integers `nums`, you are initially positioned at the first index of the array.
>
Each element in the array represents your maximum jump length at that position.
>
Your goal is to reach the last index in the minimum number of jumps.
>
You can assume that you can always reach the last index.

---

#### ***Examples:***
>
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 <= 1000
 - 0 <= nums[i] <= 10^5

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Since each element of our input array (**N**) represents the maximum jump length and not the definite jump length, that means we can visit any index between the current index (**i**) and **i + N[i]**. Stretching that to its logical conclusion, we can safely iterate through **N** while keeping track of the furthest index reachable (**next**) at any given moment (**next = max(next, i + N[i])**). We'll know we've found our solution once **next** reaches or passes the last index (**next >= N.length - 1**).

The difficulty then lies in keeping track of how many jumps it takes to reach that point. We can't simply count the number of times we update **next**, as we may see that happen more than once while still in the current jump's range. In fact, we can't be sure of the best next jump until we reach the end of the current jump's range.

So in addition to **next**, we'll also need to keep track of the current jump's endpoint (**curr**) as well as the number of jumps taken so far (**ans**).

Since we'll want to **return ans** at the earliest possibility, we should base it on **next**, as noted earlier. With careful initial definitions for **curr** and **next**, we can start our iteration at **i = 0** and **ans = 0** without the need for edge case return expressions.

 - _**Time Complexity: O(N)** where N is the length of N_
 - _**Space Cmplexity: O(1)**_

---

#### ***Implementation:***

There are only minor differences in the code of all four languages.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var jump = function(N) {
    let len = N.length - 1, curr = -1, next = 0, ans = 0
    for (let i = 0; next < len; i++) {
        if (i > curr) ans++, curr = next
        next = Math.max(next, N[i] + i)
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def jump(self, N: List[int]) -> int:
        Nlen, curr, nxt, ans, i = len(N) - 1, -1, 0, 0, 0
        while nxt < Nlen:
            if i > curr:
                ans += 1
                curr = nxt
            nxt = max(nxt, N[i] + i)
            i += 1
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int jump(int[] N) {
        int len = N.length - 1, curr = -1, next = 0, ans = 0;
        for (int i = 0; next < len; i++) {
            if (i > curr) {
                ans++;
                curr = next;
            };
            next = Math.max(next, N[i] + i);
        };
        return ans;
    };
};
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int jump(vector<int>& N) {
        int len = N.size() - 1, curr = -1, next = 0, ans = 0;
        for (int i = 0; next < len; i++) {
            if (i > curr) ans++, curr = next;
            next = max(next, N[i] + i);
        };
        return ans;
    }
};
```