{x}
blog image

Jump Game VI

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.

 

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] (underlined above). 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] (underlined above). 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 <= 105
  • -104 <= nums[i] <= 104

Solution Explanation: Jump Game VI

This problem asks to find the maximum score achievable by jumping from index 0 to the last index of an array, where each jump can be at most k steps. The score is the sum of the values visited. This can be efficiently solved using dynamic programming with a monotonic deque optimization.

Approach: Dynamic Programming with Monotonic Deque

  1. Dynamic Programming (DP): We use an array dp where dp[i] stores the maximum score achievable when reaching index i. The base case is dp[0] = nums[0].

  2. State Transition: To reach index i, we can jump from any index j such that i - k <= j < i. The maximum score achievable at i is the maximum score achievable at any of these j's, plus nums[i]:

    dp[i] = max(dp[j] + nums[i]) for i - k <= j < i

  3. Monotonic Deque Optimization: Calculating the maximum in the above equation for each i would take O(k) time, leading to an overall O(nk) time complexity. We can optimize this using a deque (double-ended queue) to maintain a monotonically decreasing sequence of dp[j] values.

    • Monotonically Decreasing: The deque will store indices j such that dp[j] values are in decreasing order from front to back. This ensures that the front of the deque always contains the index j with the maximum dp[j] value among the indices within the jump range [i - k, i - 1].

    • Deque Operations:

      • As we iterate through the nums array, we add indices to the back of the deque and remove indices from the front that are outside the current jump range (i - j > k).
      • If a new index i has a dp[i] value greater than or equal to the last element in the deque, we pop from the back until this condition is satisfied. This maintains the monotonically decreasing property.

    This optimization reduces the time complexity of finding the maximum to O(1) per index, making the overall time complexity O(n).

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of nums. The algorithm iterates through the array once, and deque operations take constant time on average.
  • Space Complexity: O(n) to store the dp array and the deque. The deque's size is at most k, but we need to store dp values.

Code Implementation (Python)

from collections import deque
 
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]  # Base case
        dq = deque([0])  # Deque to store indices
 
        for i in range(1, n):
            # Remove indices outside the jump range
            while dq and i - dq[0] > k:
                dq.popleft()
 
            # Update dp[i] using the maximum from the deque
            dp[i] = dp[dq[0]] + nums[i]
 
            # Maintain the monotonically decreasing property of the deque
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
 
            # Add the current index to the deque
            dq.append(i)
 
        return dp[n - 1]

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, utilizing a deque (or equivalent data structure) to achieve the monotonic deque optimization. The core logic and time/space complexity remain the same.