LeetCode 1696 — Jump Game VI

In this article, I will introduce how to use DP and double-ended queue to solve the LeetCode #1696, Jump Game VI.

Question:

1. Given an integer array nums and an integer k. We can jump between 1 step and k steps.
2. Each value in the nums array is a score. We want to have the maximum score that we visited.

Solution: DP + Double-ended queue

What we will think about first is DP by building a score array that stores the maximal score that ends with this index.

We then go through the nums array from the index 0 to the end. In each step, we only need to look back at the last k-1 scores by max(score[i-k, i-1]).

However, the time complexity will become O(kN) which is extremely slow when we have huge k.

Therefore, we need to only store the current maximum instead of storing everything and going over, again and again, the same values.

Here we used a double-ended queue to track the index of maximum value. This queue stores the index of values in the scores array that is monotonic decreasing. queue[0] is the index of the largest value in the queue.

• nums: array of score in each position
• scores: DP 1d-table, the array of maximal score that ends in each position
• queue: queue of the index, scores[index] are monotonic decreasing.

1. We initialize the scores array and set the first value by nums[0].
2. Then create a queue that starts only with the first index, 0.
3. For-loop starts from index 1 to n-1 to update scores array.
4. We first pop out the indices that are out of the sliding window (index < index-k). These indices won’t be able to reach the current index.
5. Check the queue from the end, whether the value (nums[qeueu.pop()]) is smaller than the current score. If Yes, then we pop the last value out. Repeat until there is no index with a value smaller than the current score.

Example code:

def maxResult(self, nums: List[int], k: int) -> int:
    k = min(k, len(nums))
    scores = [0 for i in nums] 
    scores[0] = nums[0]
    dq = deque([0])
    for idx in range(1, len(nums)):
        val = nums[idx]
        # pop out the index out side the window
        while dq and dq[0] < idx-k:
            dq.popleft()
            
        scores[idx] = scores[dq[0]] + val
            
        # pop the index with value smaller than the current score
        while dq and scores[idx] >= scores[dq[-1]]:
            dq.pop()
                
        dq.append(idx)
    return scores[-1]

Complexity:

Time complexity: O(N)

The length of for loop is N, and the length of each of two while loop is also N because each index will be appended and pop out once.

Space complexity: O(N)

We used queue and scores. The queue used at most length k, and scores array has length N. So the complexity is O(N)