LeetCode 1696 - Jump Game VI

The problem gives us an integer array nums and a maximum jump distance k. We start at index 0, and from any position i,

leetcodemediumarraydynamic-programmingqueueheap-(priority-queue)monotonic-queue

LeetCode Problem 1696

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Queue, Heap (Priority Queue), Monotonic Queue

Solution

Problem Understanding

The problem gives us an integer array nums and a maximum jump distance k. We start at index 0, and from any position i, we may jump forward to any index between i + 1 and i + k, as long as the destination remains inside the array.

Every time we land on an index, its value contributes to our score. The total score is therefore the sum of the values at all visited indices, including the starting index and the final index.

The goal is to compute the maximum possible score obtainable when reaching the last index of the array.

This is fundamentally a dynamic programming problem. At each index, we want to know the best score achievable upon arriving there. The transition looks natural:

$$dp[i] = nums[i] + \max(dp[j])$$

where j is any index in the range:

$$[i-k, i-1]$$

This means that to compute the best score for index i, we need the maximum DP value among the previous k positions.

The constraints are important:

  • 1 <= nums.length <= 10^5
  • 1 <= k <= 10^5

An O(n * k) solution is too slow in the worst case because both values can be as large as 100000. That could require up to 10^10 operations, which is far beyond acceptable limits.

The input guarantees that:

  • The array is non-empty.
  • We can always reach the last index because we may jump up to k steps forward.
  • Values may be negative, so greedy approaches that always take the locally largest number do not work.

Important edge cases include:

  • Arrays with all negative numbers.
  • Very large k, where almost every earlier position is reachable.
  • k = 1, which forces a linear walk through the array.
  • Arrays of length 1, where the answer is simply nums[0].

Approaches

Brute Force Dynamic Programming

The most direct solution uses dynamic programming.

Define dp[i] as the maximum score achievable when reaching index i.

For every index i, we examine all previous indices that can jump into it:

$$dp[i] = nums[i] + \max(dp[j])$$

for all valid:

$$j \in [i-k, i-1]$$

This solution is correct because it explicitly checks every legal transition and chooses the best one.

However, it is too slow. For each index we may scan up to k previous positions, producing a worst case complexity of:

$$O(nk)$$

With n = 100000 and k = 100000, this becomes infeasible.

Optimal Dynamic Programming with Monotonic Queue

The key observation is that every DP transition only needs the maximum value from a sliding window of the previous k DP states.

Instead of recomputing the maximum every time, we maintain a data structure that always keeps the window maximum available in constant time.

A monotonic deque works perfectly for this.

The deque stores indices of DP values in decreasing order of their DP score:

  • The front always contains the maximum DP value in the current window.
  • Indices outside the allowed range are removed from the front.
  • Smaller DP values are removed from the back because they can never become optimal again.

This reduces the complexity to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(nk) O(n) Checks every reachable previous index
Optimal O(n) O(n) Uses monotonic deque to maintain sliding maximum

Algorithm Walkthrough

  1. Create a DP array where dp[i] represents the maximum score obtainable upon reaching index i.
  2. Initialize the first position:
dp[0] = nums[0]

Since we start at index 0, this is the initial score. 3. Create a deque that will store indices of DP values in decreasing order.

Initially:

deque = [0]

The front of the deque always represents the best previous position available for the current index. 4. Iterate through the array from left to right, starting at index 1. 5. Before processing index i, remove indices from the front if they are outside the valid jump range.

If:

deque[0] < i - k

then that index can no longer jump to i, so it must be discarded. 6. The front of the deque now contains the index with the largest DP value among all valid previous positions.

Compute:

$$dp[i] = nums[i] + dp[deque[0]]$$ 7. Maintain the decreasing order of DP values inside the deque.

While the current DP value is greater than or equal to the DP value at the back of the deque:

dp[i] >= dp[deque[-1]]

remove the back index.

Those smaller values are useless because the current index is both newer and better. 8. Append the current index to the deque. 9. Continue until the last index is processed. 10. Return:

dp[n - 1]

Why it works

The deque always maintains indices in decreasing order of their DP values. Therefore, the front of the deque is always the maximum DP value within the current sliding window of size k.

Every index enters the deque once and leaves once. Because we always remove weaker candidates from the back, no unnecessary indices remain.

This guarantees that every DP transition uses the optimal previous state, producing the correct maximum score.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)

        dp = [0] * n
        dp[0] = nums[0]

        window = deque([0])

        for i in range(1, n):
            # Remove indices outside the jump range
            while window and window[0] < i - k:
                window.popleft()

            # Best previous score is at the front
            dp[i] = nums[i] + dp[window[0]]

            # Maintain decreasing dp values
            while window and dp[i] >= dp[window[-1]]:
                window.pop()

            window.append(i)

        return dp[-1]

The implementation follows the algorithm exactly.

The dp array stores the best score obtainable at every index. The first value is initialized to nums[0] because we begin there.

The deque named window stores indices, not DP values directly. This is important because we need to know when an index falls outside the valid jump window.

At each iteration, the code first removes outdated indices from the front. These positions are too far away to reach the current index.

The front of the deque always contains the best reachable previous state, so we use it immediately to compute the new DP value.

After computing dp[i], the code removes weaker candidates from the back of the deque. Any index with a smaller DP value than the current one can never become optimal in the future because the current index is both newer and stronger.

Finally, the current index is appended to the deque.

The final answer is stored at the last position of the DP array.

Go Solution

func maxResult(nums []int, k int) int {
	n := len(nums)

	dp := make([]int, n)
	dp[0] = nums[0]

	// Monotonic deque storing indices
	deque := []int{0}

	for i := 1; i < n; i++ {
		// Remove indices outside the valid range
		if deque[0] < i-k {
			deque = deque[1:]
		}

		// Best previous score
		dp[i] = nums[i] + dp[deque[0]]

		// Maintain decreasing dp values
		for len(deque) > 0 && dp[i] >= dp[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}

		deque = append(deque, i)
	}

	return dp[n-1]
}

The Go implementation mirrors the Python solution closely.

Instead of Python's deque, Go uses a slice to simulate a deque. Removing from the front is handled with slicing:

deque = deque[1:]

Appending to the back uses the built-in append function.

Go integers are sufficient because the maximum possible score remains well within 32-bit integer range, although Go's int type is typically 64-bit on modern systems anyway.

Unlike Python, Go does not have built-in dynamic deque structures, so slice manipulation is the standard approach here.

Worked Examples

Example 1

Input:

nums = [1,-1,-2,4,-7,3]
k = 2

Initial state:

Index dp Deque
0 1 [0]

Process index 1:

  • Best previous index is 0
  • dp[1] = -1 + 1 = 0

Deque maintenance:

  • dp[1] = 0
  • smaller than dp[0] = 1
  • append index 1
Index dp Deque
1 0 [0,1]

Process index 2:

  • Best previous index is 0
  • dp[2] = -2 + 1 = -1

Deque becomes:

Index dp Deque
2 -1 [0,1,2]

Process index 3:

  • Index 0 is out of range because 3 - 2 = 1
  • remove 0

Best previous index is 1

$$dp[3] = 4 + 0 = 4$$

Remove smaller values from back:

  • remove 2
  • remove 1

Deque becomes:

Index dp Deque
3 4 [3]

Process index 4:

$$dp[4] = -7 + 4 = -3$$

Deque:

Index dp Deque
4 -3 [3,4]

Process index 5:

$$dp[5] = 3 + 4 = 7$$

Remove weaker candidates:

  • remove 4
  • remove 3

Final:

Index dp Deque
5 7 [5]

Answer:

7

Example 2

Input:

nums = [10,-5,-2,4,0,3]
k = 3

DP progression:

i nums[i] Best Previous DP dp[i]
0 10 - 10
1 -5 10 5
2 -2 10 8
3 4 10 14
4 0 14 14
5 3 14 17

Final answer:

17

Example 3

Input:

nums = [1,-5,-20,4,-1,3,-6,-3]
k = 2

DP progression:

i nums[i] dp[i]
0 1 1
1 -5 -4
2 -20 -19
3 4 0
4 -1 -1
5 3 3
6 -6 -3
7 -3 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index enters and leaves the deque at most once
Space O(n) DP array plus deque storage

The algorithm is linear because every array index is processed a constant number of times. Although the deque operations occur inside loops, each element can only be inserted and removed once, so the total number of deque operations across the entire execution is proportional to n.

The DP array requires O(n) memory, and the deque may also store up to n indices in the worst case.

Test Cases

from typing import List
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]

        window = deque([0])

        for i in range(1, n):
            while window and window[0] < i - k:
                window.popleft()

            dp[i] = nums[i] + dp[window[0]]

            while window and dp[i] >= dp[window[-1]]:
                window.pop()

            window.append(i)

        return dp[-1]

sol = Solution()

assert sol.maxResult([1, -1, -2, 4, -7, 3], 2) == 7  # provided example 1
assert sol.maxResult([10, -5, -2, 4, 0, 3], 3) == 17  # provided example 2
assert sol.maxResult([1, -5, -20, 4, -1, 3, -6, -3], 2) == 0  # provided example 3

assert sol.maxResult([5], 1) == 5  # single element array
assert sol.maxResult([1, 2, 3, 4], 1) == 10  # forced linear traversal
assert sol.maxResult([1, 2, 3, 4], 4) == 10  # can still choose all positives
assert sol.maxResult([100, -100, -100, -100], 3) == 0  # large negative penalties
assert sol.maxResult([-1, -2, -3], 2) == -4  # all negative values
assert sol.maxResult([1, -1, -1, -1, 10], 2) == 10  # optimal delayed jump
assert sol.maxResult([0, 0, 0, 0], 2) == 0  # all zeros
assert sol.maxResult([1, -5, 10, -2, 3], 2) == 14  # mixed positives and negatives
assert sol.maxResult([1, -10, -10, -10, 100], 4) == 101  # long jump to large reward
Test Why
[1,-1,-2,4,-7,3], k=2 Validates standard example
[10,-5,-2,4,0,3], k=3 Tests larger jump range
[1,-5,-20,4,-1,3,-6,-3], k=2 Tests recovery from large negatives
[5], k=1 Single element edge case
[1,2,3,4], k=1 Forced sequential traversal
[1,2,3,4], k=4 Large jump window
[100,-100,-100,-100], k=3 Heavy negative penalties
[-1,-2,-3], k=2 Entirely negative input
[1,-1,-1,-1,10], k=2 Optimal path skips bad states
[0,0,0,0], k=2 Neutral values
[1,-5,10,-2,3], k=2 Mixed transitions
[1,-10,-10,-10,100], k=4 Long-range optimal jump

Edge Cases

One important edge case is an array containing only one element. In this scenario, we start at the last index immediately, so no jumps occur. A buggy implementation might incorrectly attempt deque operations or transitions that assume at least two elements exist. The implementation handles this naturally because the loop begins at index 1, which never executes when the array length is 1.

Another critical edge case occurs when all values are negative. Greedy approaches often fail here because every move reduces the score. The algorithm still works correctly because dynamic programming evaluates all reachable states and always selects the least harmful path. The deque optimization does not rely on positivity, only on relative ordering of DP values.

A third important edge case is when k = 1. In this situation, every move is forced because we may only jump to the next index. Some sliding window implementations accidentally assume multiple candidates always exist. Here, the deque effectively behaves like a single active state, and the DP reduces to a simple running sum. The implementation handles this without any special-case logic.

Another subtle case appears when k is extremely large, possibly larger than the array length. In this situation, nearly every previous index remains reachable. The deque still functions correctly because outdated indices are removed only when necessary, and the front always stores the global best DP value among reachable positions.