Solution: Jump Game VI

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #1696 (Medium): Jump Game VI

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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];
    }
};