Problem statement

https://leetcode.com/problems/jump-game-vi/

Solution

This problem is very similar to problem 239. Sliding Window Maximum, see my explained solution here https://leetcode.com/problems/sliding-window-maximum/discuss/951683/Python-Decreasing-deque-short-explained

Let us ask the question: what is the maximum score we can get when we reached index i? It is equal to nums[i] + maximum among previous k (or less if we reached boundary) numbers. The idea is exaclty the same as we use in problem 239:

  1. Let us deq be monotonic deque, that is deque, where elements inside will always decrease (in fact we keep indexes, not numbers).
  2. while deq and deq[0] < i - k: deq.popleft() this line will remove all outdated elements from our deque.
  3. nums[i] += nums[deq[0]]. Now we know that our deque is up-to-date, so we have maximum of sliding window inside it, and also because we have decreasing structure, it will be element with index 0. So, what I did here, instead of using dp array, we update elements of nums instead.
  4. while deq and nums[i] >= nums[deq[-1]]: deq.pop(). We want to add new element i, and we need to keep our deque decreasing, so we remove as much element as needed to keep this invariant, and then put element i to the end.

Complexity

Time complexity is just O(n), because for each index i it will be at most once put to deque and removed from deque. Space complexity is O(k).

Code

class Solution:
    def maxResult(self, nums, k):
        deq, n = deque([0]), len(nums)

        for i in range(1, n):
            while deq and deq[0] < i - k: deq.popleft()
            nums[i] += nums[deq[0]]   
            while deq and nums[i] >= nums[deq[-1]]: deq.pop()
            deq.append(i)
            
        return nums[-1]

Remark

As this problem is closely connected with problem 239, you can in fact use any method which was working there. I know at least 2 other approaches: one is BST with complexity O(n log k) and another is heaps with lazy updates with complexity O(n log n).