Solution: Jump Game VI
Tags: algorithms, javascript, java, python
Published: 2021-06-09 19:52:51

*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-vi/discuss/1261753).*

---

#### [Leetcode Problem #1696 (*Medium*): Jump Game VI](https://leetcode.com/problems/jump-game-vi/)

---

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

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

>
You are given a **0-indexed** integer array `nums` and an integer `k`.
>
You are initially standing at index `0`. In one move, you can jump at most `k` steps forward without going outside the boundaries of the array. That is, you can jump from index `i` to any index in the range `[i + 1, min(n - 1, i + k)]` **inclusive**.
>
You want to reach the last index of the array (index `n - 1`). Your **score** is the **sum** of all `nums[j]` for each index `j` you visited in the array.
>
Return _the **maximum score** you can get_.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| nums = [1,-1,-2,4,-7,3], k = 2
Output:| 7
Explanation:| You can choose your jumps forming the subsequence [1,-1,_,4,_,3]. The sum is 7.
>
Example 2:||
|---:|---|
Input:| nums = [10,-5,-2,4,0,3], k = 3
Output:| 17
Explanation:| You can choose your jumps forming the subsequence [10,_,_,4,_,3]. The sum is 17.
>
Example 3:||
|---:|---|
Input:| nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output:| 0

---

#### ***Constraints:***
>
 - `1 <= nums.length, k <= 10^5`
 - `-10^4 <= nums[i] <= 10^4`

---

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

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

For this problem, we can see that there are many possible paths from one end of **nums** to the other, but that they cross back over each other countless times. There may be multiple ways to get to a given element in the middle of **nums**, but there should only be one best way to get from there to the end of **nums**.

When we find ourselves potentially solving the same subproblem over and over again, it's time for a **dynamic programming** (**DP**) approach. In a normal DP approach, we would create a DP array to store the best solution from each element to the end, but since we're only going to be iterating through **nums** once, we can use an **in-place DP** approach and modify the elements of **nums** as we iterate through.

_(**Note**: If you choose not to modify your inputs, you can make a separate DP array to store these values. This will increase the **space complexity** to **O(N)**.)_

Now, if we consider being located at a particular element in **nums**, and all the elements ahead of us having been modified to equal the best value to the end of **nums**, then the best value for the current location will be its own value plus the best value it can reach in a jump of up to **k** distance.

One option here would be to use a **priority queue** to keep track of the best results ahead, then we could just take the top value in the priority queue (while remembering to first remove any entries that are farther than **k** distance away). But a priority queue isn't terribly efficient for our purposes.

Instead, we can use a **double-ended queue** (**deq**) to good effect here. Since we'll need to remove elements from the front end of **deq** if they're outside the jump window, we should use indexes for the **deq** entries.

When we go to push an index onto **deq**, we should consider that any indexes at the end of **deq** which represent lower values will never be used, as they will always be surpassed by the newer value until they fall outside the jump window. Before pushing the new index onto **deq** then, we should remove from the end of **deq** any indexes representing lower values.

This consequently means that **deq** will always be sorted from high to low values, which is precisely what we wanted. At every iteration (**i**) then, after removing out-of-window indexes, the top entry will represent the value we want to add to **nums[i]** to equal the best result from **i** to the end of **nums**.

We can continue this iteration down to **i = 0**, then **return nums[0]** as the finished result.

 - _**Time Complexity: O(N)** where **N** is the length of **nums**_
 - _**Space Complexity: O(K)** for **deq**_
   - _or **O(N)** if we use a separate DP array rather than modifying **nums**_

---

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

For Java, the **ArrayDeque()** implementation is much slower than using an **int array** with the same length as **nums** and then using a **sliding window** with pointers (**a, b**) to represent the current first and last element of **deq**. This will push the **space complexity** to **O(N)**.

The same applies to C++ and their implementation of **deque()**, though to a lesser degree.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var maxResult = function(nums, k) {
   let n = nums.length, deq = [n-1]
    for (let i = n - 2; ~i; i--) {
        if (deq[0] - i > k) deq.shift()
        nums[i] += nums[deq[0]]
        while (deq.length && nums[deq[deq.length-1]] <= nums[i]) deq.pop()
        deq.push(i)
    }
    return nums[0] 
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        deq = deque([n-1])
        for i in range(n-2, -1, -1):
            if deq[0] - i > k: deq.popleft()
            nums[i] += nums[deq[0]]
            while len(deq) and nums[deq[-1]] <= nums[i]: deq.pop()
            deq.append(i)
        return nums[0]
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length, a = 0, b = 0;
        int[] deq = new int[n];
        deq[0] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (deq[a] - i > k) a++;
            nums[i] += nums[deq[a]];
            while (b >= a && nums[deq[b]] <= nums[i]) b--;
            deq[++b] = i;
        }
        return nums[0];
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size(), a = 0, b = 0;
        int deq[n];
        deq[0] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (deq[a] - i > k) a++;
            nums[i] += nums[deq[a]];
            while (b >= a && nums[deq[b]] <= nums[i]) b--;
            deq[++b] = i;
        }
        return nums[0];
    }
};
```