Jump Game VI
Understanding the Problem
We start at index 0 and must reach index n-1. From any position i, we can jump forward by 1 to k positions. Every index we land on adds nums[j] to our score, and we want to maximize that total score.
Two details shape the solution. The values can be negative, so when k is small we may be forced through low-value indices we would rather skip. And this is a pathfinding problem, not a subsequence selection problem: we choose a route from index 0 to index n-1 where consecutive steps are at most k apart, and we must land on the last index.
That structure gives a natural recurrence. Define dp[i] as the maximum score to reach index i starting from index 0. To arrive at i, we jump from some index j in the range [max(0, i-k), i-1], then add nums[i]. We want the best such j, so dp[i] = nums[i] + max(dp[j]) over that range. The base case is dp[0] = nums[0], and the answer is dp[n-1].
Key Constraints:
1 <= nums.length <= 10^5: With n up to 100,000, an O(n*k) approach degrades to O(n^2) when k is close to n, which is too slow. We need O(n log n) or O(n).-10^4 <= nums[i] <= 10^4: Negative values mean we cannot skip indices freely. When k is small, the path may be forced through negatives.1 <= k <= nums.length: When k = n, we can jump from index 0 directly to n-1, so the answer isnums[0] + nums[n-1]. When k = 1, we must visit every index. Scores fit comfortably in a 32-bit int (worst case about 10^5 indices times 10^4, near 10^9), so no overflow concern.
Approach 1: Dynamic Programming (Brute Force)
Intuition
Compute dp[i] directly from the recurrence. For each index, look back at the previous k positions, take the highest dp value among them, and add nums[i] because we land on index i. The base case is dp[0] = nums[0], and the answer is dp[n-1].
Finding the maximum is a plain scan of the window [max(0, i-k), i-1]. That scan is what the later approaches replace.
Algorithm
- Create a dp array of size n. Set
dp[0] = nums[0]. - For each index
ifrom 1 to n-1, look back at all dp values in the range[max(0, i-k), i-1]. - Find the maximum among those dp values.
- Set
dp[i] = nums[i] + maxPrev. - Return
dp[n-1].
Example Walkthrough
Code
- Time Complexity: O(n * k). For each of the n elements, we scan up to k previous dp values to find the maximum. When k approaches n, this degrades to O(n^2).
- Space Complexity: O(n). We store the dp array of size n.
The inner loop rescans almost the same window at every step. The next approach tracks the window maximum with a data structure so we no longer scan from scratch.
Approach 2: DP with Heap (Priority Queue)
Intuition
A max-heap tracks the dp values seen so far and returns the maximum in O(1) at the top, with O(log n) insertions. The complication is that the entry at the top may belong to an index that has already fallen out of the window [i-k, i-1]. To handle this, store both the dp value and its index in the heap, and before reading the top, pop any entries whose index is below i - k. This is lazy deletion: stale entries linger in the heap until they reach the top, at which point we discard them. Each index is inserted and removed at most once, so the deletions cost O(1) amortized.
Algorithm
- Create a max-heap. Set
dp[0] = nums[0]and push(dp[0], 0)into the heap. - For each index
ifrom 1 to n-1: - While the top of the heap has an index less than
i - k, pop it (it's outside the window). - The heap's top now gives the best dp value within jump range.
- Set
dp[i] = nums[i] + heap_top_value. - Push
(dp[i], i)into the heap. - Return
dp[n-1].
Example Walkthrough
Code
- Time Complexity: O(n log n). Each element is pushed into and popped from the heap at most once. Each push/pop costs O(log n).
- Space Complexity: O(n). The heap can hold up to n elements in the worst case, plus the dp array.
The heap maintains more order than we need: we only ever read the maximum. The next approach keeps only the indices that could still become the window maximum, which brings the cost down to O(n).
Approach 3: DP with Monotonic Deque (Optimal)
Intuition
This is the sliding window maximum technique applied to the DP recurrence. Instead of a full heap, maintain a deque of indices whose dp values decrease from front to back. The front always holds the index with the largest dp value in the current window, so reading the maximum is an O(1) lookup with no sorting.
The deque stays decreasing because of a dominance argument. Take two indices j < i with dp[j] <= dp[i]. For any future position, i is both newer (it stays in the window at least as long as j) and at least as good a predecessor. So j can never be the unique best choice, and discarding it loses nothing. Removing all such dominated indices from the back before inserting i is what keeps the sequence decreasing, and it guarantees the front is always the window maximum.
The work is O(n) because each index is pushed once and popped once. A single step may pop several indices from the back, but the total number of pops across the whole run cannot exceed the number of pushes, which is n.
Algorithm
- Create a deque that stores indices. Initialize with index 0, set
dp[0] = nums[0]. - For each index
ifrom 1 to n-1: - Remove indices from the front of the deque that are outside the window (index < i - k).
- The front of the deque gives the index with the maximum dp value in the window.
- Set
dp[i] = nums[i] + dp[deque.front()]. - Before pushing
ionto the back, remove all indices from the back whose dp values are less than or equal todp[i](they're dominated and will never be needed). - Push
ionto the back of the deque. - Return
dp[n-1].
Example Walkthrough
Code
- Time Complexity: O(n). Each index is pushed to and popped from the deque at most once. All deque operations are O(1). Total work is O(n).
- Space Complexity: O(n). The dp array takes O(n). The deque holds at most n indices in the worst case, though typically far fewer.