Jump Game VI — Monotonic Deque for Sliding Window Max DP

Problem Statement#

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 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 visit (including the starting index 0 and the ending index n - 1).

Return the maximum score you can get.

Constraints:

• 1 <= nums.length, k <= 10^5
• -10^4 <= nums[i] <= 10^4

Input:  nums = [1,-1,-2,4,-7,3], k = 2
Output: 7   // path 1 -> -1 -> 4 -> 3

Input:  nums = [10,-5,-2,4,0,3], k = 3
Output: 17  // path 10 -> 4 -> 3

Why This Problem Matters#

LeetCode 1696 Jump Game VI is one of the cleanest examples of pairing dynamic programming with a monotonic deque. It is asked at Amazon, Google, Meta, and TikTok because it forces the candidate to recognize that a naive O(n times k) DP is too slow for n equal to 100000 and k equal to 100000, and to reach for the sliding window maximum technique.

This problem is the bridge between two foundational patterns: 1D DP and monotonic deque. Mastering this combination unlocks Sliding Window Maximum (LeetCode 239), Constrained Subsequence Sum (LeetCode 1425), and Shortest Subarray with Sum at Least K (LeetCode 862). If you can write this in your sleep, you can solve a significant slice of the medium-to-hard FAANG bar.

The Core Insight#

Define dp[i] as the maximum score to reach index i. The recurrence is:

dp[i] equals nums[i] plus max over j in the range from i minus k to i minus 1 of dp[j].

The naive evaluation costs O(k) per index for an O(n times k) total — too slow.

Notice that we are computing the maximum over a sliding window of width k of the dp array. This is exactly the Sliding Window Maximum problem. A monotonic decreasing deque solves it in amortized O(1) per index:

• The deque stores indices whose dp values form a decreasing sequence from front to back.
• The front always holds the index with the maximum dp in the current window.
• When we move to index i, pop expired indices from the front (those out of the window i minus k). Then while the back's dp is less than or equal to dp[i], pop the back (since they are dominated by the more recent and larger value). Push i.

Total time becomes O(n) because every index is pushed and popped at most once.

Visual Dry Run#

nums equals [1, -1, -2, 4, -7, 3], k equals 2.

Answer dp[5] equals 7. The deque never holds more than k plus 1 items, so memory is bounded.

Solution (Optimal)#

The deque holds indices, not values, so we can detect when the front index falls outside the window of width k. We maintain decreasing dp values from front to back.

from collections import deque
from typing import List
 
def maxResult(nums: List[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])  # indices with decreasing dp values
 
    for i in range(1, n):
        # Remove indices out of the window [i - k, i - 1]
        while dq and dq[0] < i - k:
            dq.popleft()
 
        dp[i] = nums[i] + dp[dq[0]]
 
        # Maintain monotonic decreasing dp values
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
 
    return dp[n - 1]

function maxResult(nums, k) {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  const dq = [0];
  let head = 0;
  for (let i = 1; i < n; i++) {
    while (head < dq.length && dq[head] < i - k) head++;
    dp[i] = nums[i] + dp[dq[head]];
    while (dq.length > head && dp[dq[dq.length - 1]] <= dp[i]) dq.pop();
    dq.push(i);
  }
  return dp[n - 1];
}

Complexity. Time O(n) because each index is pushed and popped from the deque at most once. Space O(n) for the dp array plus O(k) for the deque.

Common Mistakes#

• Using a max-heap instead of a monotonic deque. A heap costs O(log n) per push and lazy-deletion adds bugs. The deque is strictly better for sliding windows.
• Storing values in the deque instead of indices. You must be able to detect when the front falls out of the window, which requires the index.
• Using strict less-than when popping the back. Equality should also pop because newer equal values are preferable (longer reach).
• Forgetting to seed dp[0] equal to nums[0] and starting the deque empty.
• Using a Python list with pop(0) instead of collections.deque. pop(0) is O(n) and will TLE on large inputs.

Interview Tips#

• Always state the brute force first and compute its complexity out loud. Then introduce the sliding window maximum reframing.
• Draw the deque on a whiteboard for the first three to four iterations. Interviewers want to see that you understand why the deque is monotonic.
• Articulate the invariant: "the front of the deque is always the argmax of dp over the current window."
• Mention that this technique is general — it solves any DP whose transition is a max or min over a sliding window of fixed width.
• Discuss the trade-off versus a segment tree (O(n log n)) and explain why the deque wins for fixed window widths.

Follow-up Questions#

1. What if you can also choose to skip the segment entirely and pay a cost? Add a "skip" branch to the recurrence; the deque structure still applies.
2. What if k is variable per index? The window width changes; you may need a segment tree or sparse table.
3. What if you want to reconstruct the path? Store the argmax index alongside each dp value; backtrack from n minus 1.
4. What if scores can be negative everywhere — does the deque still help? Yes; the deque is height-agnostic. Negative scores just lower dp values uniformly.
5. What if k equals n? The window covers everything; dp[i] equals nums[i] plus max(dp[0..i-1]). The deque still gives O(n).

Key Takeaways#

• Jump Game VI is the textbook DP plus monotonic deque combination problem.
• A monotonic decreasing deque on indices gives amortized O(1) sliding-window max queries.
• The deque must hold indices, not values, so you can evict elements outside the window.
• This pattern generalizes to any DP whose transition is a max or min over a fixed-width window.
• Time O(n), space O(n) — a perfect FAANG-grade improvement over the O(n times k) naive solution.
• Mastering this unlocks LeetCode 239, 862, 1425 and many sliding window maximum variants.