1696. Jump Game VI


Problem Description

In this problem, you're given an integer array nums and another integer k. The nums array represents a series of spots that you can stand on, and the value at each spot represents the score you can receive for standing there. The objective is to get from the first index (0) of the array to the last index (n - 1, n being the length of the array), accumulating the maximum possible score.

You can jump from your current index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive. This means that at any point, you may take a leap forward by up to k steps, but no further, and you cannot jump outside the array boundaries. Each time you land on an index, you add up the values (nums[j]) from each of the indices j that you've visited. Your "score" is the sum of these values.

The challenge is to figure out which set of jumps will yield the highest possible score by the time you reach the end of the array.

Intuition

To solve this problem and find the path with the maximum score, one might consider using Dynamic Programming (DP). The DP approach works here because at each index, the best score only depends on the previous decisions, and we are looking for an overall maximum.

The intuition behind the solution can be likened to a 'sliding window' of possibilities for each jump, constrained by k. In DP terms, this window represents subproblems you need to solve on your way to the overall problem's solution. For each index i, you try to find the maximum score you could have if you landed on that index considering the best you could do to get to any permissible previous index.

Key Steps:

  1. Initialization: Create an array f of the same length as nums to store the maximum score at each index.

  2. Deque to Store Candidates: Use a deque q to keep indices of the array that are potential candidates for jumping to the next index. The deque is maintained in decreasing order of scores; the front always holds the maximum score attainable.

  3. Iterate Each Index:

    • If the first element in the deque is more than k distance from the current index, remove it from the deque because it's no longer a valid jump option.
    • Calculate the current index's max score by adding the value at nums[i] to the score at the front of the deque (which represents the best previous score within a k-sized window).
    • Remove elements from the end of the deque as long as the score corresponding to the indices is less than or equal to the score at current index i because they would never contribute to a higher score in the future (due to the k constraint).
  4. Append Current Index:

    • After adjusting the deque to maintain the decreasing order of scores, append the current index to it.
  5. Return Score at Last Index: The last element of f (f[-1]) will hold the maximum score you could get upon reaching the end of the array.

Using this approach, the solution achieves an optimal balance between computing maximum scores and maintaining an efficient way to discard non-competitive options. The deque ensures that removal and addition of candidates are done in constant time, thus keeping the overall time complexity manageable.

Learn more about Queue, Dynamic Programming, Monotonic Queue and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The problem's solution employs the Dynamic Programming (DP) technique and a deque data structure to keep track of the potential indices that could give us the maximum score upon reaching each position.

  1. Dynamic Initialization:
1f = [0] * n
2q = deque([0])

Here, f is initialized with zeros for all indices in nums. This array f will store the maximum score at each index as we traverse the array. The deque q is initialized with the first index (0) since our starting position is index 0.

  1. Iterate Through nums:

For each index i in the range [0, n):

  • Bound Check: If the current index i is out of the k-range from the first element in the deque, it means we can no longer jump from that element's index to i, and thus we remove it from the deque:
1if i - q[0] > k:
2    q.popleft()
  • Calculate Score: The score at f[i] is computed as the sum of nums[i] and the score at f[q[0]] (as q[0] holds the index of the maximum score within k distance):
1f[i] = nums[i] + f[q[0]]
  • Maintain Decreasing Order in Deque: Before adding the current index to the deque, we pop from the deque's end while the score at the end is less than or equal to the current index's score. This is done because if f[current] is greater than or equal to f[deque's last element], then the last element will never be used as it's not going to contribute to a maximum score:
1while q and f[q[-1]] <= f[i]:
2    q.pop()
  • Add Current Index to Deque: Finally, append the current index i to the deque q because it could potentially be the index from which a future position jumps to get a maximum score:
1q.append(i)
  1. Return Maximum Score: At the end of the loop, since we have computed the score for each index, the final score at the last index n-1 is the maximum score that can be obtained by any jump sequence, so we return it:
1return f[-1]

The algorithm uses DP to efficiently calculate the maximum score at each index based on the best possible previous indices and uses a deque to maintain a sliding window of indices that are potential candidates to jump from, for each index i. The use of a doubly-ended queue allows for efficient addition and removal of indices from both ends, which is crucial for ensuring the algorithm's time efficiency.

By utilizing DP combined with a sliding-window approach, the solution can efficiently tackle the challenge posed by the problem, keeping a running tally of the best scores for each index, and always having a quick access to the best score from which to "jump" to the next potential index in the window defined by k.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

To illustrate the solution approach, let's use a small example. Consider the array nums = [10, -5, 2, 4, 0, 3] and k = 2.

We want to find the maximum score we can get by the time we reach the end of the array following the jumping rules defined by k.

Initialization

We initialize an array f to store the maximum scores and a deque q to keep track of potential jumping indices.

1f = [0, 0, 0, 0, 0, 0]  # Based on `nums` length
2q = deque([0])

Iteration #1

Starting at index 0, nums[0] is 10, so f[0] will also be 10 (since it's the start point).

Iteration #2

Moving to index 1:

  • No elements are removed from q since i - q[0] is 1 - 0 which is not greater than k (2).
  • We calculate f[1] to be nums[1] + f[q[0]], which is -5 + 10 = 5.
  • Since f[1] is less than f[0], we do not remove anything from q.
  • We append 1 to q.

The arrays become: f = [10, 5, 0, 0, 0, 0], q = deque([0, 1]).

Iteration #3

At index 2:

  • No elements from q are removed.
  • f[2] is nums[2] + f[q[0]] which is 2 + 10 = 12.
  • Now, f[2] is greater than f[1], so we pop 1 from q.
  • We append 2 to q.

Now f = [10, 5, 12, 0, 0, 0], q = deque([0, 2]).

Iteration #4

At index 3:

  • We remove 0 from q since 3 - q[0] (0) is greater than k.
  • f[3] is nums[3] + f[q[0]] which is 4 + 12 = 16.
  • f[3] is greater than f[2], so we pop 2 from q.
  • We append 3 to q.

Arrays update to: f = [10, 5, 12, 16, 0, 0], q = deque([3]).

Iteration #5

At index 4:

  • No elements from q are removed.
  • Calculate f[4] as nums[4] + f[q[0]] which is 0 + 16 = 16.
  • No changes to q, as f[4] is equal to f[3].
  • We append 4 to q.

We have: f = [10, 5, 12, 16, 16, 0], q = deque([3, 4]).

Iteration #6

Finally, at index 5:

  • No elements from q are removed.
  • Calculate f[5] as nums[5] + f[q[0]] which is 3 + 16 = 19.
  • Since f[5] is greater than f[4], we pop 4 from q.
  • Append 5 to q.

The complete f array is f = [10, 5, 12, 16, 16, 19]. The q is deque([5]).

Return Maximum Score

The last element in f, f[-1], is the answer, which is 19. This is the maximum score achievable.

Summary

In this example walkthrough, the maximum score calculation has been demonstrated step by step using an example array and the process of maintaining a deque q for optimal substructure discovery, as well as dynamic programming array f for storing intermediate results. The process ensures that at every step, the most optimal choice for the next jump is made while also pruning choices that will no longer be beneficial for future jumps.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def maxResult(self, nums: List[int], k: int) -> int:
6        # Determine the total number of elements in 'nums'.
7        length = len(nums)
8      
9        # Initialize the array that will store the maximum score up to each index.
10        max_scores = [0] * length
11      
12        # Initialize a double-ended queue to store indices of 'nums' elements.
13        # This queue will help us find the maximum score in the sliding window.
14        indices_deque = deque([0])
15
16        # Iterate over all the elements in 'nums'.
17        for i in range(length):
18            # Check if the oldest index in 'indices_deque' is outside the window of size 'k'.
19            # If it is, we remove it from the deque.
20            if i - indices_deque[0] > k:
21                indices_deque.popleft()
22          
23            # The current score at index 'i' is the value of 'nums[i]' plus
24            # the maximum score within the range 'i - k' to 'i - 1'.
25            max_scores[i] = nums[i] + max_scores[indices_deque[0]]
26          
27            # While the deque is not empty and the maximum score at index 'i'
28            # is greater than or equal to the score at the last index in 'indices_deque',
29            # pop indices from the deque. This ensures that the deque will always
30            # maintain elements in descending order of their max_scores.
31            while indices_deque and max_scores[indices_deque[-1]] <= max_scores[i]:
32                indices_deque.pop()
33          
34            # Append the current index 'i' to 'indices_deque'.
35            indices_deque.append(i)
36      
37        # The last element in 'max_scores' array represents the maximum score
38        # that can be obtained by jumping from index 0 to the last index.
39        return max_scores[-1]
40
1class Solution {
2    public int maxResult(int[] nums, int k) {
3        // The length of the given array.
4        int n = nums.length;
5        // An array to store the maximum score that can be achieved upto that index.
6        int[] dp = new int[n];
7        // A deque to keep track of indexes whose scores are relevant for the current position.
8        Deque<Integer> indexDeque = new ArrayDeque<>();
9        indexDeque.offer(0);
10      
11        for (int i = 0; i < n; ++i) {
12            // If the current index is out of the range of k from the start of the deque,
13            // remove that index as it is no longer relevant.
14            if (i - indexDeque.peekFirst() > k) {
15                indexDeque.pollFirst();
16            }
17          
18            // The maximum score at the current index is the sum of the value at this index
19            // and the maximum score within the last k indexes.
20            dp[i] = nums[i] + dp[indexDeque.peekFirst()];
21          
22            // If the score at the current index is greater than or equal to the score at
23            // the indexes stored at the end of the deque, remove those indexes.
24            while (!indexDeque.isEmpty() && dp[indexDeque.peekLast()] <= dp[i]) {
25                indexDeque.pollLast();
26            }
27          
28            // Add the current index to the end of the deque as it might be useful
29            // for the upcoming indexes.
30            indexDeque.offerLast(i);
31        }
32      
33        // Return the maximum score that can be achieved at the last index.
34        return dp[n - 1];
35    }
36}
37
1class Solution {
2public:
3    int maxResult(vector<int>& nums, int k) {
4        int numElements = nums.size(); // Number of elements in nums array
5        vector<int> dp(numElements); // Create a dynamic programming array to store maximum scores
6        dp[0] = nums[0]; // The score of the first element is the element itself
7        deque<int> maxDeque; // Create a double-ended queue to store indices of maximum scores
8      
9        // Initialize the deque with the index of the first element
10        maxDeque.push_back(0);
11      
12        // Iterate over the array starting from the second element
13        for (int i = 1; i < numElements; ++i) {
14            // If the first element in the deque is out of the current window, remove it
15            if (i - maxDeque.front() > k) maxDeque.pop_front();
16          
17            // The current score is the sum of the current element and
18            // the maximum score within the window of the last k elements
19            dp[i] = nums[i] + dp[maxDeque.front()];
20          
21            // Maintain elements in the deque in decreasing order to easily find the max
22            while (!maxDeque.empty() && dp[maxDeque.back()] <= dp[i]) {
23                maxDeque.pop_back();
24            }
25          
26            // Add the current index to the deque
27            maxDeque.push_back(i);
28        }
29
30        // The last element of dp array is the answer
31        return dp[numElements - 1];
32    }
33};
34
1function maxResult(nums: number[], k: number): number {
2    let numElements: number = nums.length; // Number of elements in the nums array
3    let dp: number[] = new Array(numElements); // Dynamic programming array to store maximum scores
4    dp[0] = nums[0]; // The score of the first element is the element itself
5    let maxDeque: number[] = []; // Double-ended queue to store indices of maximum scores within a window of size k
6
7    // Initialize the deque with the index of the first element
8    maxDeque.push(0);
9
10    // Iterate over the array starting from the second element
11    for (let i = 1; i < numElements; ++i) {
12        // If the first element in the deque is out of the current window, remove it from the front
13        if (i - maxDeque[0] > k) {
14            maxDeque.shift();
15        }
16
17        // The current score is the sum of the current element and
18        // the maximum score within the window of the last k elements
19        dp[i] = nums[i] + dp[maxDeque[0]];
20
21        // Maintain elements in the deque in decreasing order to easily find the max
22        while (maxDeque.length > 0 && dp[maxDeque[maxDeque.length - 1]] <= dp[i]) {
23            maxDeque.pop();
24        }
25
26        // Add the current index to the deque
27        maxDeque.push(i);
28    }
29
30    // The value at the last index of the dp array is the maximum score
31    return dp[numElements - 1];
32}
33
Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the length of the input array nums. The main loop runs once for each element of the array. In that loop, the following operations occur:

  • Checking if i - q[0] > k and popping from the left of the deque: In total, each index will be added and then removed exactly once throughout the entire loop. Therefore, these deque operations will not exceed O(n) over the course of the entire loop.

  • Appending to the deque happens once for every element, which provides a time contribution of O(n) across all iterations.

  • The while loop pops elements from the deque if f[q[-1]] <= f[i]. Each element will at most be popped once since an element is removed only if a new optimum is found, which is an O(1) operation per element. Therefore, this while loop will, in aggregate, not exceed O(n) over all the iterations.

Hence, the algorithm has a linear time complexity due to the deque operations being amortized over all the iterations.

Space Complexity

The space complexity of the code consists of the space required for:

  • The list f, which takes up O(n) space.

  • The deque q, which in the worst case, can contain all the elements of the list if the elements of nums are non-increasing, also leading to O(n) space.

Thus, taking into account the space required for the input and auxiliary data structures, the total space complexity would be O(n) as well.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫