Problem editorial

Jump Game VI

MediumSliding WindowArrayDynamic ProgrammingQueue

Editorial

Core insight

Jump Game VI · Sliding Window

Core Insight for Jump Game VI

The core difficulty in the brute force approach is repeatedly scanning the previous k elements to find the maximum dp value. This is identical to the "Sliding Window Maximum" problem.

By maintaining a Monotonic Decreasing Queue (specifically a Deque), we can access the maximum value in the current window in $O(1)$ time.

The Deque stores indices of the dp array. We enforce an invariant where the values corresponding to these indices are strictly decreasing.

Front of Deque: Always holds the index of the maximum dp value in the current valid window [i-k, i-1].
Back of Deque: Used to maintain the monotonic property. When we compute a new dp[i], it might be larger than previous values. If dp[i] is larger than dp[back], the back index is useless (it is smaller and will expire sooner), so we remove it.

Visual Description: Imagine iterating through the array. As you calculate dp[i], you look at the front of the deque to get the best previous score. After calculating dp[i], you treat it as a candidate for future jumps. You insert i into the back of the deque. Before inserting, you pop any indices from the back that have a smaller dp value than dp[i]. This ensures the deque remains sorted by score descending. Finally, you check the front; if the index at the front is too old (outside the k range), you pop it.

Sliding Window - Monotonic Queue for Max/Min Pattern Visualization for LeetCode 1696: Jump Game VI

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 1696: Jump Game VI Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses Dynamic Programming combined with a Monotonic Deque to find the maximum score in linear time, avoiding the quadratic complexity of a naive search.

In LeetCode 1696: Jump Game VI, you are given an integer array nums and an integer k. Starting at index 0, you must reach the last index (n-1). In each step, you can jump to any index within the next k positions. The goal is to maximize the sum of elements at the indices you visit.

This is a classic optimization problem often seen in technical interviews. It requires finding the best path through an array where the "best" decision at the current step depends on the optimal outcomes of previous steps within a fixed window.

Brute Force Approach for Jump Game VI

The most intuitive way to solve this is using Dynamic Programming (DP). Let dp[i] represent the maximum score achievable to reach index i. To calculate dp[i], we look at the previous k indices (from i-k to i-1) and choose the one with the maximum score, then add nums[i].

The recurrence relation is: $dp[i] = nums[i] + \max(dp[i-k], dp[i-k+1], \dots, dp[i-1])$

Naive Pseudo-code

python

1dp = array of size n
2dp[0] = nums[0]
3
4for i from 1 to n-1:
5    max_prev = -infinity
6    # Check the last k positions
7    for j from 1 to k:
8        if i - j >= 0:
9            max_prev = max(max_prev, dp[i - j])
10    dp[i] = nums[i] + max_prev
11
12return dp[n-1]

Time Complexity Analysis

This approach has a time complexity of $O(N \cdot K)$ . For every element i, we iterate up to k times backward. Given the constraints where $N \le 10^5$ and $K \le 10^5$ , the total operations could reach $10^{10}$ in the worst case. This will result in a Time Limit Exceeded (TLE) error. We need a way to find the maximum in the range [i-k, i-1] faster than $O(K)$ .

Algorithm Strategy: Sliding Window Patterns

We will maintain a DP array (or modify nums in place) and a Deque to store indices.

Initialization:
- Create a DP array where dp[0] = nums[0].
- Initialize a Deque and add index 0.
Iteration:
- Loop from i = 1 to n - 1.
Window Maintenance (Front):
- Check if the index at the front of the Deque is out of the jump range (i.e., front < i - k). If so, remove it.
State Calculation:
- The maximum score from the previous k steps is simply dp[deque.front()].
- Set dp[i] = nums[i] + dp[deque.front()].
Monotonic Maintenance (Back):
- Before adding i to the Deque, compare dp[i] with the dp value of the index at the back of the Deque.
- While the Deque is not empty and dp[i] >= dp[deque.back()], remove the back element. The new score dp[i] is better and more recent, rendering the smaller previous scores obsolete.
- Add i to the back of the Deque.
Result:
- Return dp[n - 1].

Execution Flow

Let's trace nums = [1, -1, -2, 4, -7, 3] and k = 2.

Init: dp[0] = 1. Deque q = [0].
i = 1:
- Window check: q.front() is 0. Valid since 0 >= 1 - 2.
- Calc: dp[1] = nums[1] + dp[0] = -1 + 1 = 0.
- Maintain: dp[1] (0) vs dp[q.back()] (1). 0 < 1, no pop.
- Push 1. q = [0, 1].
i = 2:
- Window check: q.front() is 0. Valid since 0 >= 2 - 2.
- Calc: dp[2] = nums[2] + dp[0] = -2 + 1 = -1.
- Maintain: dp[2] (-1) vs dp[q.back()] (0). -1 < 0, no pop.
- Push 2. q = [0, 1, 2].
i = 3:
- Window check: q.front() is 0. Invalid (0 < 3 - 2). Pop front. q is now [1, 2].
- Calc: dp[3] = nums[3] + dp[1] = 4 + 0 = 4.
- Maintain:
  - dp[3] (4) > dp[2] (-1). Pop 2. q = [1].
  - dp[3] (4) > dp[1] (0). Pop 1. q = [].
- Push 3. q = [3].
i = 4:
- Window check: q.front() is 3. Valid.
- Calc: dp[4] = -7 + 4 = -3.
- Maintain: -3 < 4. Push 4. q = [3, 4].
i = 5:
- Window check: q.front() is 3. Valid.
- Calc: dp[5] = 3 + 4 = 7.
- Maintain: 7 > -3 (pop 4), 7 > 4 (pop 3). Push 5. q = [5].
End: Return dp[5] = 7.

Proof of Correctness

The algorithm relies on the principle of optimality in Dynamic Programming: the optimal path to index i is formed by extending the optimal path to some index j (where i-k <= j < i).

The correctness hinges on the Monotonic Deque correctly maintaining the maximum dp value in the sliding window.

Completeness: Since we remove indices only when they fall out of the window (< i-k) or are strictly smaller than a newer value, the largest valid value is always preserved.
Ordering: The deque is strictly decreasing. Therefore, the first element is always the maximum within the current window. Thus, dp[i] is always calculated using the true maximum of the preceding k states, ensuring the global maximum score is found.

Pattern Reuse Notes

The Sliding Window - Monotonic Queue pattern is powerful for optimization problems involving contiguous subarrays or fixed ranges.

LeetCode 239: Sliding Window Maximum - This is the foundational problem for this pattern. Jump Game VI is essentially applying LeetCode 239 logic on the DP array as it is being built.
LeetCode 862: Shortest Subarray with Sum At Least K - Uses a Monotonic Queue on prefix sums to find the shortest subarray meeting a sum constraint. The logic of maintaining indices to satisfy a monotonicity constraint is identical.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 1696

cpp

1#include <vector>
2#include <deque>
3
4using namespace std;
5
6class Solution {
7public:
8    int maxResult(vector<int>& nums, int k) {
9        int n = nums.size();
10        vector<int> dp(n);
11        dp[0] = nums[0];
12        
13        // Deque stores indices of potential max scores
14        deque<int> dq;
15        dq.push_back(0);
16        
17        for (int i = 1; i < n; ++i) {
18            // 1. Remove indices that are out of the current window (i - k)
19            if (!dq.empty() && dq.front() < i - k) {
20                dq.pop_front();
21            }
22            
23            // 2. The max score in the window is at the front of the deque
24            dp[i] = nums[i] + dp[dq.front()];
25            
26            // 3. Maintain monotonicity: remove indices with scores <= current score
27            while (!dq.empty() && dp[dq.back()] <= dp[i]) {
28                dq.pop_back();
29            }
30            
31            // 4. Add current index to the deque
32            dq.push_back(i);
33        }
34        
35        return dp[n - 1];
36    }
37};

Java Solution for LeetCode 1696

java

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    public int maxResult(int[] nums, int k) {
6        int n = nums.length;
7        int[] dp = new int[n];
8        dp[0] = nums[0];
9        
10        // Deque stores indices, ordered by dp value descending
11        Deque<Integer> deque = new ArrayDeque<>();
12        deque.offerLast(0);
13        
14        for (int i = 1; i < n; i++) {
15            // 1. Remove indices out of window [i-k, i-1]
16            if (!deque.isEmpty() && deque.peekFirst() < i - k) {
17                deque.pollFirst();
18            }
19            
20            // 2. Calculate dp[i] using the max from the window (front of deque)
21            dp[i] = nums[i] + dp[deque.peekFirst()];
22            
23            // 3. Maintain monotonicity: remove elements smaller than current dp[i]
24            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
25                deque.pollLast();
26            }
27            
28            // 4. Add current index
29            deque.offerLast(i);
30        }
31        
32        return dp[n - 1];
33    }
34}

Python Solution for LeetCode 1696

python

1from collections import deque
2
3class Solution:
4    def maxResult(self, nums: list[int], k: int) -> int:
5        n = len(nums)
6        dp = [0] * n
7        dp[0] = nums[0]
8        
9        # Deque stores indices
10        q = deque([0])
11        
12        for i in range(1, n):
13            # 1. Remove indices out of window
14            if q[0] < i - k:
15                q.popleft()
16            
17            # 2. Calculate current max score
18            # q[0] is the index of the max score in the previous k steps
19            dp[i] = nums[i] + dp[q[0]]
20            
21            # 3. Maintain Monotonicity (Decreasing)
22            # Remove indices from back if their dp value is <= current dp[i]
23            while q and dp[q[-1]] <= dp[i]:
24                q.pop()
25            
26            # 4. Add current index
27            q.append(i)
28            
29        return dp[n - 1]

AI Coach Insight

For Jump Game VI, focus on explaining why the structure works, not just naming Sliding Window.

Complexity Analysis

Time Complexity: $O(N)$

We iterate through the array once.
Each index is added to the Deque exactly once and removed at most once.
Deque operations (push, pop, front, back) are $O(1)$ .
Thus, the total work is linear relative to the size of nums.

Space Complexity: $O(N)$

We use an array of size $N$ to store DP states. (This can be optimized to $O(K)$ or $O(1)$ if we overwrite nums).
The Deque stores at most $K+1$ indices in the worst case.
Overall space is dominated by the DP array.

Related Patterns

Pattern: Sliding Window Patterns
Subpattern: Sliding Window - Monotonic Queue for Max/Min

This problem fits the Sliding Window - Monotonic Queue pattern perfectly because we need to query the maximum value within a moving window of fixed size k as we iterate through the array to compute DP states.

Common Mistakes & FAQ

Why does the naive solution TLE?
- Mistake: Using nested loops to scan k elements backwards for every index.
- Reasoning: This results in $O(N \cdot K)$ complexity. With $N, K = 10^5$ , this is too slow.
- Consequence: The solution fails on large test cases due to timeout.
Why store indices instead of values in the Deque?
- Mistake: Storing the actual dp values in the Deque.
- Reasoning: We need to know when a value falls out of the sliding window (index i - k). If we only store values, we cannot determine if the maximum value is still reachable from the current index i.
- Consequence: The algorithm may use a "maximum" value that is actually too far away to jump from, leading to incorrect answers.
Why use a Deque instead of a Priority Queue (Heap)?
- Mistake: Using a Max Heap to store the window.
- Reasoning: While a Heap works, removing elements that are out of the window is tricky (lazy removal) and operations are $O(\log K)$ . The Monotonic Deque approach is strictly $O(1)$ amortized per element.
- Consequence: A Heap solution is $O(N \log K)$ , which is acceptable but less optimal than the $O(N)$ Deque solution.
Checking the window bounds incorrectly
- Mistake: Using if front < i - k - 1 or similar off-by-one errors.
- Reasoning: The valid range is strictly [i - k, i - 1]. If the index is i - k - 1, it is k + 1 steps away, which is too far.
- Consequence: Logic errors leading to wrong answers.

Practise Jump Game VI and the problems around it

Jump Game VI is a Sliding Window problem, in the Monotonic Queue for Max/Min subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Jump Game VI · Sliding Window

Core Insight for Jump Game VI

The core difficulty in the brute force approach is repeatedly scanning the previous k elements to find the maximum dp value. This is identical to the "Sliding Window Maximum" problem.

By maintaining a Monotonic Decreasing Queue (specifically a Deque), we can access the maximum value in the current window in $O(1)$ time.

The Deque stores indices of the dp array. We enforce an invariant where the values corresponding to these indices are strictly decreasing.

Front of Deque: Always holds the index of the maximum dp value in the current valid window [i-k, i-1].
Back of Deque: Used to maintain the monotonic property. When we compute a new dp[i], it might be larger than previous values. If dp[i] is larger than dp[back], the back index is useless (it is smaller and will expire sooner), so we remove it.

Sliding Window - Monotonic Queue for Max/Min Pattern Visualization for LeetCode 1696: Jump Game VI

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 1696: Jump Game VI Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses Dynamic Programming combined with a Monotonic Deque to find the maximum score in linear time, avoiding the quadratic complexity of a naive search.

Brute Force Approach for Jump Game VI

The recurrence relation is: $dp[i] = nums[i] + \max(dp[i-k], dp[i-k+1], \dots, dp[i-1])$

Naive Pseudo-code

python

1dp = array of size n
2dp[0] = nums[0]
3
4for i from 1 to n-1:
5    max_prev = -infinity
6    # Check the last k positions
7    for j from 1 to k:
8        if i - j >= 0:
9            max_prev = max(max_prev, dp[i - j])
10    dp[i] = nums[i] + max_prev
11
12return dp[n-1]

Time Complexity Analysis

Algorithm Strategy: Sliding Window Patterns

We will maintain a DP array (or modify nums in place) and a Deque to store indices.

Initialization:
- Create a DP array where dp[0] = nums[0].
- Initialize a Deque and add index 0.
Iteration:
- Loop from i = 1 to n - 1.
Window Maintenance (Front):
- Check if the index at the front of the Deque is out of the jump range (i.e., front < i - k). If so, remove it.
State Calculation:
- The maximum score from the previous k steps is simply dp[deque.front()].
- Set dp[i] = nums[i] + dp[deque.front()].
Monotonic Maintenance (Back):
- Before adding i to the Deque, compare dp[i] with the dp value of the index at the back of the Deque.
- While the Deque is not empty and dp[i] >= dp[deque.back()], remove the back element. The new score dp[i] is better and more recent, rendering the smaller previous scores obsolete.
- Add i to the back of the Deque.
Result:
- Return dp[n - 1].

Execution Flow

Let's trace nums = [1, -1, -2, 4, -7, 3] and k = 2.

Init: dp[0] = 1. Deque q = [0].
i = 1:
- Window check: q.front() is 0. Valid since 0 >= 1 - 2.
- Calc: dp[1] = nums[1] + dp[0] = -1 + 1 = 0.
- Maintain: dp[1] (0) vs dp[q.back()] (1). 0 < 1, no pop.
- Push 1. q = [0, 1].
i = 2:
- Window check: q.front() is 0. Valid since 0 >= 2 - 2.
- Calc: dp[2] = nums[2] + dp[0] = -2 + 1 = -1.
- Maintain: dp[2] (-1) vs dp[q.back()] (0). -1 < 0, no pop.
- Push 2. q = [0, 1, 2].
i = 3:
- Window check: q.front() is 0. Invalid (0 < 3 - 2). Pop front. q is now [1, 2].
- Calc: dp[3] = nums[3] + dp[1] = 4 + 0 = 4.
- Maintain:
  - dp[3] (4) > dp[2] (-1). Pop 2. q = [1].
  - dp[3] (4) > dp[1] (0). Pop 1. q = [].
- Push 3. q = [3].
i = 4:
- Window check: q.front() is 3. Valid.
- Calc: dp[4] = -7 + 4 = -3.
- Maintain: -3 < 4. Push 4. q = [3, 4].
i = 5:
- Window check: q.front() is 3. Valid.
- Calc: dp[5] = 3 + 4 = 7.
- Maintain: 7 > -3 (pop 4), 7 > 4 (pop 3). Push 5. q = [5].
End: Return dp[5] = 7.

Proof of Correctness

The algorithm relies on the principle of optimality in Dynamic Programming: the optimal path to index i is formed by extending the optimal path to some index j (where i-k <= j < i).

The correctness hinges on the Monotonic Deque correctly maintaining the maximum dp value in the sliding window.

Completeness: Since we remove indices only when they fall out of the window (< i-k) or are strictly smaller than a newer value, the largest valid value is always preserved.
Ordering: The deque is strictly decreasing. Therefore, the first element is always the maximum within the current window. Thus, dp[i] is always calculated using the true maximum of the preceding k states, ensuring the global maximum score is found.

Pattern Reuse Notes

The Sliding Window - Monotonic Queue pattern is powerful for optimization problems involving contiguous subarrays or fixed ranges.

LeetCode 239: Sliding Window Maximum - This is the foundational problem for this pattern. Jump Game VI is essentially applying LeetCode 239 logic on the DP array as it is being built.
LeetCode 862: Shortest Subarray with Sum At Least K - Uses a Monotonic Queue on prefix sums to find the shortest subarray meeting a sum constraint. The logic of maintaining indices to satisfy a monotonicity constraint is identical.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 1696

cpp

1#include <vector>
2#include <deque>
3
4using namespace std;
5
6class Solution {
7public:
8    int maxResult(vector<int>& nums, int k) {
9        int n = nums.size();
10        vector<int> dp(n);
11        dp[0] = nums[0];
12        
13        // Deque stores indices of potential max scores
14        deque<int> dq;
15        dq.push_back(0);
16        
17        for (int i = 1; i < n; ++i) {
18            // 1. Remove indices that are out of the current window (i - k)
19            if (!dq.empty() && dq.front() < i - k) {
20                dq.pop_front();
21            }
22            
23            // 2. The max score in the window is at the front of the deque
24            dp[i] = nums[i] + dp[dq.front()];
25            
26            // 3. Maintain monotonicity: remove indices with scores <= current score
27            while (!dq.empty() && dp[dq.back()] <= dp[i]) {
28                dq.pop_back();
29            }
30            
31            // 4. Add current index to the deque
32            dq.push_back(i);
33        }
34        
35        return dp[n - 1];
36    }
37};

Java Solution for LeetCode 1696

java

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class Solution {
5    public int maxResult(int[] nums, int k) {
6        int n = nums.length;
7        int[] dp = new int[n];
8        dp[0] = nums[0];
9        
10        // Deque stores indices, ordered by dp value descending
11        Deque<Integer> deque = new ArrayDeque<>();
12        deque.offerLast(0);
13        
14        for (int i = 1; i < n; i++) {
15            // 1. Remove indices out of window [i-k, i-1]
16            if (!deque.isEmpty() && deque.peekFirst() < i - k) {
17                deque.pollFirst();
18            }
19            
20            // 2. Calculate dp[i] using the max from the window (front of deque)
21            dp[i] = nums[i] + dp[deque.peekFirst()];
22            
23            // 3. Maintain monotonicity: remove elements smaller than current dp[i]
24            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
25                deque.pollLast();
26            }
27            
28            // 4. Add current index
29            deque.offerLast(i);
30        }
31        
32        return dp[n - 1];
33    }
34}

Python Solution for LeetCode 1696

python

1from collections import deque
2
3class Solution:
4    def maxResult(self, nums: list[int], k: int) -> int:
5        n = len(nums)
6        dp = [0] * n
7        dp[0] = nums[0]
8        
9        # Deque stores indices
10        q = deque([0])
11        
12        for i in range(1, n):
13            # 1. Remove indices out of window
14            if q[0] < i - k:
15                q.popleft()
16            
17            # 2. Calculate current max score
18            # q[0] is the index of the max score in the previous k steps
19            dp[i] = nums[i] + dp[q[0]]
20            
21            # 3. Maintain Monotonicity (Decreasing)
22            # Remove indices from back if their dp value is <= current dp[i]
23            while q and dp[q[-1]] <= dp[i]:
24                q.pop()
25            
26            # 4. Add current index
27            q.append(i)
28            
29        return dp[n - 1]

Jump Game VI

Core insight

Core Insight for Jump Game VI

Full breakdown

LeetCode 1696: Jump Game VI Solution & Explanation

Problem Overview

Brute Force Approach for Jump Game VI

Naive Pseudo-code

Time Complexity Analysis

Algorithm Strategy: Sliding Window Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 1696

Java Solution for LeetCode 1696

Python Solution for LeetCode 1696

Practise Jump Game VI and the problems around it

Related problems

Jump Game VI

Core insight

Core Insight for Jump Game VI

Full breakdown

LeetCode 1696: Jump Game VI Solution & Explanation

Problem Overview

Brute Force Approach for Jump Game VI

Naive Pseudo-code

Time Complexity Analysis

Algorithm Strategy: Sliding Window Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 1696

Java Solution for LeetCode 1696

Python Solution for LeetCode 1696

Practise Jump Game VI and the problems around it

Related problems