Jump Game VI
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward dynamic programming solution. We define dp[i] as the maximum score achievable to reach index i. To compute dp[i], we need to find the maximum score among all possible previous indices j from which we can jump to i. These indices j are in the range [i - k, i - 1]. The recurrence relation is dp[i] = nums[i] + max(dp[j]) for j in [max(0, i - k), i - 1]. We build up the dp array from the beginning to the end.
Algorithm
- Create a DP array
dpof sizen, wherenis the length ofnums. - Initialize
dp[0] = nums[0], as the score to reach the first index is just its value. - Iterate with a loop from
i = 1ton - 1. - Inside this loop, create another loop to find the maximum score among the previous
kreachable indices. Let this bemax_prev. The inner loop iterates fromj = 1tok(as long asi - jis a valid index). - Update
dp[i] = nums[i] + max_prev. - After the outer loop finishes,
dp[n - 1]will hold the maximum score to reach the last index.
Walkthrough
We can solve this problem using dynamic programming. Let's define dp[i] as the maximum score to reach index i. Our goal is to find dp[n-1].
Base Case:
The base case is dp[0] = nums[0], because we start at index 0 and its score is included.
Recurrence Relation:
For any index i > 0, we can reach it from any index j such that i - k <= j < i. To maximize the score at i, we must have come from the previous index j that had the maximum score. Therefore, the score at i is nums[i] plus the maximum score in the window dp[i-k...i-1].
dp[i] = nums[i] + max(dp[i-1], dp[i-2], ..., dp[i-k])
We can implement this by iterating from i = 1 to n-1 and, for each i, iterating again through the last k indices to find the maximum dp value.
class Solution { public int maxResult(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { int maxPrev = Integer.MIN_VALUE; for (int j = 1; j <= k && i - j >= 0; j++) { maxPrev = Math.max(maxPrev, dp[i - j]); } dp[i] = nums[i] + maxPrev; } return dp[n - 1]; }}Complexity
Time
O(N * K), where N is the number of elements in `nums`. For each element `i`, we look back at `k` previous elements.
Space
O(N) to store the `dp` array.
Trade-offs
Pros
Simple to understand and implement.
It correctly formulates the problem as a dynamic programming recurrence.
Cons
The time complexity of O(N * K) is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
The bottleneck in the basic DP approach is the repeated search for the maximum value in a sliding window. This can be optimized. Instead of a linear scan, we can use a data structure that provides the maximum element more efficiently. A max heap (or a priority queue) is a suitable choice. We can maintain a max heap of the scores of the last k indices. For each step i, we find the maximum score in the window [i-k, i-1] by looking at the top of the heap, after removing outdated entries.
Algorithm
- Initialize a max heap (Priority Queue in Java) to store pairs of
[score, index]. - The heap will be ordered by score in descending order.
- Start by adding the first element's score and index to the heap:
pq.offer(new int[]{nums[0], 0}). - Initialize a variable
maxScoretonums[0]. - Iterate from
i = 1ton - 1. - Inside the loop, first, remove any elements from the top of the heap whose indices are outside the current window (i.e.,
index < i - k). - The element at the top of the heap now represents the maximum score in the valid
k-sized window. Get this score. - Calculate the score for the current index
iascurrent_score = nums[i] + pq.peek()[0]. - Update
maxScore = current_score. - Add the new
[current_score, i]to the heap. - After the loop,
maxScorewill be the result for the last index.
Walkthrough
To improve upon the O(N*K) complexity, we need a faster way to find the maximum in the sliding window dp[i-k...i-1]. A max heap can find the maximum element in O(1) time (peeking) and supports insertions in O(log K) time. The heap will store pairs of (score, index).
As we iterate from i = 1 to n-1:
- We first prune the heap by removing all elements
(score, j)wherejis no longer in the current window (i.e.,j < i - k). - The top of the heap now gives us the maximum score from a valid preceding index. Let this be
max_prev_score. - We calculate the score for the current index
iascurrent_score = nums[i] + max_prev_score. - We then add
(current_score, i)to the heap.
This process ensures that for each i, we can find the required maximum in O(log K) time on average, leading to a much better overall time complexity.
import java.util.PriorityQueue; class Solution { public int maxResult(int[] nums, int k) { int n = nums.length; // PriorityQueue stores pairs of [score, index] PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); int maxScore = nums[0]; pq.offer(new int[]{nums[0], 0}); for (int i = 1; i < n; i++) { // Remove elements from the heap that are outside the window of size k while (pq.peek()[1] < i - k) { pq.poll(); } // The top of the heap is the max score in the current window int[] top = pq.peek(); maxScore = nums[i] + top[0]; // Add the current score and index to the heap pq.offer(new int[]{maxScore, i}); } return maxScore; }}Complexity
Time
O(N log K). Each of the N elements is pushed and popped from the heap at most once. Heap operations take O(log K) time, as the heap size is bounded by `k`.
Space
O(K) to store at most `k` elements in the priority queue.
Trade-offs
Pros
Much more efficient than the naive DP approach, and it's fast enough to pass the given constraints.
The logic is a standard optimization for sliding window problems.
Cons
Slightly more complex to implement due to the use of a Priority Queue.
The logarithmic factor in the time complexity makes it less efficient than the optimal O(N) solution.
This approach provides the most optimal solution by using a deque to solve the sliding window maximum problem in linear time. We maintain a deque of indices such that the dp values corresponding to these indices are in a monotonically decreasing order. This structure allows us to find the maximum in the current window in O(1) time by simply looking at the front of the deque. Each index is added to and removed from the deque at most once, leading to an amortized O(1) time per step.
Algorithm
- Initialize a double-ended queue (deque) to store indices.
- We will use the input array
numsto store the DP scores to save space.nums[i]will be updated to hold the max score to reach indexi. - Add the starting index
0to the deque. - Iterate from
i = 1ton - 1. - First, remove indices from the front of the deque that are outside the window
[i-k, i-1]. Check ifdq.peekFirst() < i - k. - The index at the front of the deque,
dq.peekFirst(), now corresponds to the maximum score in the valid window. Update the current score:nums[i] = nums[i] + nums[dq.peekFirst()]. - To maintain the monotonic property, remove all indices from the back of the deque whose scores are less than or equal to the new score
nums[i]. - Add the current index
ito the back of the deque. - The final answer is
nums[n-1].
Walkthrough
The problem of finding the maximum in a sliding window can be solved most efficiently in O(N) time using a double-ended queue (deque). The deque will store indices of nums.
We maintain a special property in the deque: it stores indices j1, j2, ..., jm such that j1 < j2 < ... < jm and the corresponding scores dp[j1] > dp[j2] > ... > dp[jm]. This is a monotonically decreasing deque with respect to the scores.
As we iterate from i = 0 to n-1:
- Window Maintenance: Remove indices from the front of the deque that are no longer in the current window of size
k. That is, ifdq.front() <= i - k - 1, remove it. - Calculate Score: The maximum score in the window is now at
dp[dq.front()]. We calculate the current scoredp[i] = nums[i] + dp[dq.front()]. We can use thenumsarray itself to store thedpvalues to optimize space. - Maintain Monotonicity: Before adding
ito the deque, we remove all indicesjfrom the back of the deque ifdp[j] <= dp[i]. This ensures that the deque remains monotonically decreasing. - Add Index: Add the current index
ito the back of the deque.
This process ensures that the head of the deque always holds the index of the maximum element in the current window, and each element is processed in amortized constant time.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public int maxResult(int[] nums, int k) { int n = nums.length; // Deque stores indices of nums Deque<Integer> dq = new ArrayDeque<>(); // Start with the first element's index dq.offerLast(0); for (int i = 1; i < n; i++) { // 1. Remove indices from the front that are out of the window [i-k, i-1] if (dq.peekFirst() < i - k) { dq.pollFirst(); } // 2. The front of the deque has the index with the max score in the window. // Update nums[i] to store the max score to reach this point. nums[i] = nums[i] + nums[dq.peekFirst()]; // 3. Maintain the monotonic decreasing property of the deque. // Remove indices from the back whose scores are less than the current score. while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) { dq.pollLast(); } // 4. Add the current index to the deque. dq.offerLast(i); } return nums[n - 1]; }}Complexity
Time
O(N), where N is the number of elements. Each index is pushed and popped from the deque at most once, and all deque operations are O(1).
Space
O(K) for the deque, which stores at most `k` indices. If we modify the input array `nums` in-place, no extra space for a DP array is needed.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(K).
It's a very efficient and standard technique for sliding window problems.
Cons
The logic for maintaining the monotonic deque can be less intuitive than the heap-based approach for beginners.
Solutions
Solution
class Solution {public int maxResult(int[] nums, int k) { int n = nums.length; int[] f = new int[n]; Deque<Integer> q = new ArrayDeque<>(); q.offer(0); for (int i = 0; i < n; ++i) { if (i - q.peekFirst() > k) { q.pollFirst(); } f[i] = nums[i] + f[q.peekFirst()]; while (!q.isEmpty() && f[q.peekLast()] <= f[i]) { q.pollLast(); } q.offerLast(i); } return f[n - 1]; }}class Solution {public: int maxResult(vector<int> &nums, int k) { int n = nums.size(); int f[n]; f[0] = 0; deque<int> q = {0}; for (int i = 0; i < n; ++i) { if (i - q.front() > k) q.pop_front(); f[i] = nums[i] + f[q.front()]; while (!q.empty() && f[q.back()] <= f[i]) q.pop_back(); q.push_back(i); } return f[n - 1]; }};class Solution : def maxResult ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) f = [ 0 ] * n q = deque ([ 0 ]) for i in range ( n ): if i - q [ 0 ] > k : q . popleft () f [ i ] = nums [ i ] + f [ q [ 0 ]] while q and f [ q [ - 1 ]] <= f [ i ]: q . pop () q . append ( i ) return f [ - 1 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.