What is the brute force approach and complexity for Jump Game VI?

dp[i] = nums[i] + max of the last k dp values, found by a loop with time complexity O(N · K) and space complexity O(N).

What is the optimal approach and complexity for Jump Game VI?

Deque of indices with decreasing dp; front = best index in reach with optimal time complexity O(N) and space complexity O(K).

How do you identify the pattern for Jump Game VI?

Look for key signals in the prompt: "jump forward by 1 to k steps" indicates dp[i] depends on a window of the last k states.; "maximum score" indicates We need the **max** over that window — a sliding window maximum.; "sum of every index you land on" indicates dp[i] = nums[i] + best previous dp. The window max is over dp values, which are only known as we go..

Jump Game VI

Medium·LeetCode #1696Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP + Monotonic Decreasing Deque (sliding window max over dp)

Complexity:O(N · K)→O(N)

Key Insight

Keep a deque of indices whose dp values decrease from front to back. For each i: drop the front if it is out of reach (< i − k). The front is now the best index to jump from, so dp[i] = nums[i] + dp[front]. Then pop from the back every index with dp ≤ dp[i] and push i.

Core Validity Invariant

An index is still useful only if it is in reach (index ≥ i − k) and no newer index has a dp value ≥ it.

Problem

You are given an integer array nums and a number k. You start on index 0.

In one move you can jump forward by 1 to k steps, as long as you stay inside the array. So from index i you can land on any index from i + 1 to min(n − 1, i + k).

Your score is the sum of nums[j] over every index j you land on, including index 0 and the last index. You must end on the last index, n − 1.

Return the maximum score you can get.

Input

An integer array nums of length n, and an integer k.

Output

A single integer: the best possible score.

Example 1

Input: nums = [1, -1, -2, 4, -7, 3], k = 2

Output: 7

Land on 1 → -1 → 4 → 3. The score is 1 − 1 + 4 + 3 = 7. You must skip -2 and -7, and with k = 2 you can't skip two in a row.

Example 2

Input: nums = [10, -5, -2, 4, 0, 3], k = 3

Output: 17

Land on 10 → 4 → 3. Jumping 3 steps from 10 skips both negatives. Score 17.

Example 3

Input: nums = [1, -5, -20, 4, -1, 3, -6, -3], k = 2

Output: 0

One best path is 1 → -5 → 4 → 3 → -3, which gives 0.

Constraints

• 1 ≤ n, k ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I already knew the best score to reach every earlier index, how would I get the best score for index i?
2.
From which indices can I land on index i?
3.
Is index i − k one of them, or not?
4.
When I move from i to i + 1, how does the set of indices I can come from change?
5.
Once a newer index has a score at least as good as an older one, will the older one ever be the best place to jump from?

Brute force approach

Idea

Fill dp from left to right. For each i, loop over j from max(0, i − k) to i − 1, take the largest dp[j], and add nums[i].

Thinking process

1
Trying every path is exponential, but the best path to i only depends on where you came from.
2
Whatever path got you to j, you want the best one. So store dp[j] = best score to reach j.
3
Then dp[i] = nums[i] + the best dp[j] among the indices that can reach i.
4
Check all of them with a loop.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        // dp[i] = best score of a path that starts at 0 and ends at i.
        vector<int> dp(n);
        dp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            // We reached i from one of the last k indices. Try them all.
            int best = INT_MIN;
            for (int j = max(0, i - k); j < i; j++) {
                best = max(best, dp[j]);
            }
            dp[i] = nums[i] + best;
        }
        return dp[n - 1];
    }
};

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        // dp[i] = best score of a path that starts at 0 and ends at i.
        int[] dp = new int[n];
        dp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            // We reached i from one of the last k indices. Try them all.
            int best = Integer.MIN_VALUE;
            for (int j = Math.max(0, i - k); j < i; j++) {
                best = Math.max(best, dp[j]);
            }
            dp[i] = nums[i] + best;
        }
        return dp[n - 1];
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # dp[i] = best score of a path that starts at 0 and ends at i.
        dp = [0] * n
        dp[0] = nums[0]

        for i in range(1, n):
            # We reached i from one of the last k indices. Try them all.
            best = float('-inf')
            for j in range(max(0, i - k), i):
                best = max(best, dp[j])
            dp[i] = nums[i] + int(best)

        return dp[n - 1]

export function maxResult(nums: number[], k: number): number {
    const n = nums.length;
    // dp[i] = best score of a path that starts at 0 and ends at i.
    const dp = new Array(n);
    dp[0] = nums[0];

    for (let i = 1; i < n; i++) {
        // We reached i from one of the last k indices. Try them all.
        let best = -Infinity;
        for (let j = Math.max(0, i - k); j < i; j++) {
            best = Math.max(best, dp[j]);
        }
        dp[i] = nums[i] + best;
    }
    return dp[n - 1];
}

Complexity

Time O(N · K)Space O(N)

With n = k = 10^5 that is up to 10^10 steps — too slow. (Plain recursion trying every path, without dp, would be exponential.)

Better approach

Why brute force is slow

For every index we loop over up to k earlier dp values to find their max.

What repeated work are we doing?

Neighbouring indices look at almost the same k values — the window only gains one index and loses one.

What information can we reuse?

Keep the earlier dp values in a max-heap that survives from one step to the next. Each step only adds one value and pops expired tops.

New approach

Idea

Push every (dp[j], j) into a max-heap. For i, look at the top. If its index is < i − k, it is out of reach — pop it and look again. The first top that is in reach is the best one.

Thinking process

1
The brute force re-scans k values for every i, even though the window only changes by one index.
2
I need "max of a sliding window", with values that arrive one at a time. A heap gives the max quickly.
3
Removing old indices from a heap is awkward, so don't: only throw an index away when it shows up on top and is too old. That is lazy removal.

Code & Implementation

better.cpp

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        // Max-heap of (dp value, index). The top is the best dp seen so far,
        // but it may be too far back to jump from.
        priority_queue<pair<int, int>> pq;
        pq.push({dp[0], 0});

        for (int i = 1; i < n; i++) {
            // Lazy removal: only throw away an old index when it reaches the top.
            // Index i - k is still allowed (a jump of exactly k).
            while (pq.top().second < i - k) {
                pq.pop();
            }
            dp[i] = nums[i] + pq.top().first;
            pq.push({dp[i], i});
        }
        return dp[n - 1];
    }
};

import java.util.*;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        // Max-heap of (dp value, index). The top is the best dp seen so far,
        // but it may be too far back to jump from.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        pq.offer(new int[] { dp[0], 0 });

        for (int i = 1; i < n; i++) {
            // Lazy removal: only throw away an old index when it reaches the top.
            // Index i - k is still allowed (a jump of exactly k).
            while (pq.peek()[1] < i - k) {
                pq.poll();
            }
            dp[i] = nums[i] + pq.peek()[0];
            pq.offer(new int[] { dp[i], i });
        }
        return dp[n - 1];
    }
}

import heapq
from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        # Max-heap of (-dp value, index). The top is the best dp seen so far,
        # but it may be too far back to jump from.
        pq: List[Tuple[int, int]] = [(-dp[0], 0)]

        for i in range(1, n):
            # Lazy removal: only throw away an old index when it reaches the top.
            # Index i - k is still allowed (a jump of exactly k).
            while pq[0][1] < i - k:
                heapq.heappop(pq)
            dp[i] = nums[i] - pq[0][0]
            heapq.heappush(pq, (-dp[i], i))

        return dp[n - 1]

class MaxHeap {
    private data: [number, number][] = [];

    push(val: [number, number]): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): [number, number] | undefined {
        if (this.data.length === 0) return undefined;
        const max = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return max;
    }

    peek(): [number, number] | undefined {
        return this.data[0];
    }

    size(): number {
        return this.data.length;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.data[parent][0] < this.data[idx][0]) {
                [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let largest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.data[left][0] > this.data[largest][0]) largest = left;
            if (right < len && this.data[right][0] > this.data[largest][0]) largest = right;
            if (largest !== idx) {
                [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
                idx = largest;
            } else {
                break;
            }
        }
    }
}

export function maxResult(nums: number[], k: number): number {
    const n = nums.length;
    const dp = new Array(n);
    dp[0] = nums[0];
    // Max-heap of (dp value, index). The top is the best dp seen so far,
    // but it may be too far back to jump from.
    const pq = new MaxHeap();
    pq.push([dp[0], 0]);

    for (let i = 1; i < n; i++) {
        // Lazy removal: only throw away an old index when it reaches the top.
        // Index i - k is still allowed (a jump of exactly k).
        while (pq.peek()![1] < i - k) {
            pq.pop();
        }
        dp[i] = nums[i] + pq.peek()![0];
        pq.push([dp[i], i]);
    }
    return dp[n - 1];
}

Complexity

Time O(N log N)Space O(N)

Expired entries can stay deep inside the heap, so it can grow to n entries. Fast enough to pass, but a monotonic deque does the same job in O(N).

Optimized approach

Idea

Start from brute force

The brute force computes dp[i] by scanning the last k dp values for their max, for every i.

Find the repeated work

Those windows overlap almost completely, so the same dp values are compared up to k times. And many of them can never win: an older index with a lower (or equal) score than a newer one is beaten for good.

Define the state — what variables do I need?

dp[i]: The best score of a path that starts at 0 and ends on index i.
dq: Deque of indices from the last k positions. Their dp values strictly decrease from front to back, so the front is the best place to jump from.
i: The index being computed. You can land on it from i − k … i − 1.

Define validity

An index is still useful only if it is in reach (index ≥ i − k) and no newer index has a dp value ≥ it.

Define the transitions — when does each pointer move, and why is it safe?

dq.front() < i − k

dq.pop_front()

From that index the longest jump falls short of i, and it falls even shorter for later indices. Only the front can be this old, since indices in the deque increase from front to back.

Always, after the front check

dp[i] = nums[i] + dp[dq.front()]

The front has the largest dp among the indices that can reach i.

dp[dq.back()] ≤ dp[i]

dq.pop_back()

i is newer, so it stays in reach longer, and its score is at least as good. The back index will never be the best place to jump from again.

After the pops

dq.push_back(i)

i may become the best jump-off point once the bigger scores in front of it go out of reach.

What does the current window add to the answer?

Each index gets its dp value once. The answer is dp[n − 1], because the path must end on the last index.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        // dq stores INDICES. Their dp values decrease from front to back,
        // so the front is always the best place to jump from.
        deque<int> dq;
        dq.push_back(0);

        for (int i = 1; i < n; i++) {
            // We can jump from i-k .. i-1. Index i-k is still in range,
            // so only drop indices that are strictly smaller than i-k.
            if (dq.front() < i - k) {
                dq.pop_front();
            }
            dp[i] = nums[i] + dp[dq.front()];

            // dp[i] is newer and at least as good as these, so they can
            // never be the best jump-off point again. Throw them away.
            while (!dq.empty() && dp[dq.back()] <= dp[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        return dp[n - 1];
    }
};

import java.util.*;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        // dq stores INDICES. Their dp values decrease from front to back,
        // so the front is always the best place to jump from.
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offerLast(0);

        for (int i = 1; i < n; i++) {
            // We can jump from i-k .. i-1. Index i-k is still in range,
            // so only drop indices that are strictly smaller than i-k.
            if (dq.peekFirst() < i - k) {
                dq.pollFirst();
            }
            dp[i] = nums[i] + dp[dq.peekFirst()];

            // dp[i] is newer and at least as good as these, so they can
            // never be the best jump-off point again. Throw them away.
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        return dp[n - 1];
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        # dq stores INDICES. Their dp values decrease from front to back,
        # so the front is always the best place to jump from.
        dq: Deque[int] = deque([0])

        for i in range(1, n):
            # We can jump from i-k .. i-1. Index i-k is still in range,
            # so only drop indices that are strictly smaller than i-k.
            if dq[0] < i - k:
                dq.popleft()
            dp[i] = nums[i] + dp[dq[0]]

            # dp[i] is newer and at least as good as these, so they can
            # never be the best jump-off point again. Throw them away.
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)

        return dp[n - 1]

export function maxResult(nums: number[], k: number): number {
    const n = nums.length;
    const dp = new Array(n);
    dp[0] = nums[0];
    // dq stores INDICES. Their dp values decrease from front to back,
    // so the front is always the best place to jump from.
    const dq: number[] = [0];
    let head = 0;

    for (let i = 1; i < n; i++) {
        // We can jump from i-k .. i-1. Index i-k is still in range,
        // so only drop indices that are strictly smaller than i-k.
        if (dq[head] < i - k) {
            head++;
        }
        dp[i] = nums[i] + dp[dq[head]];

        // dp[i] is newer and at least as good as these, so they can
        // never be the best jump-off point again. Throw them away.
        while (dq.length > head && dp[dq[dq.length - 1]] <= dp[i]) {
            dq.pop();
        }
        dq.push(i);
    }
    return dp[n - 1];
}

Complexity

Time O(N)Space O(K)

Each index is pushed once and popped at most once. The dp array is O(N), but it can be dropped by storing dp values next to the indices in the deque.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	dp[i] = nums[i] + max of the last k dp values, found by a loop	O(N · K)	O(N)
Better	Keep (dp, index) in a max-heap; pop tops that are out of reach	O(N log N)	O(N)
Optimal	Deque of indices with decreasing dp; front = best index in reach	O(N)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“jump forward by 1 to k steps”dp[i] depends on a window of the last k states.
“maximum score”We need the **max** over that window — a sliding window maximum.
“sum of every index you land on”dp[i] = nums[i] + best previous dp. The window max is over dp values, which are only known as we go.

dp[i] = value + best of the last k dp values+window slides one step each time+need the window max→DP + Monotonic Decreasing Deque (sliding window max over dp)

This is the anchor of the deque-DP sub-pattern. The deque is the same as in Sliding Window Maximum; the only new thing is that the values in the window are dp values you compute on the fly. The next question, Constrained Subsequence Sum, uses the same deque but lets you start fresh (max(0, …)) and end anywhere.

Don't make this mistake

Off-by-one window: dropping index i − k

✗ if (dq.front() <= i - k) dq.pop_front();

✓ if (dq.front() < i - k) dq.pop_front();

A jump of exactly k is allowed, so i − k can still reach i. Dropping it loses the best path in cases like [1, -10, -10, 1], k = 3, where the answer 2 needs a jump of exactly 3.

Pushing i before computing dp[i]

✗ while (...) dq.pop_back(); dq.push_back(i); dp[i] = nums[i] + dp[dq.front()];

✓ dp[i] = nums[i] + dp[dq.front()]; while (...) dq.pop_back(); dq.push_back(i);

The back pops compare dp[i], which doesn't exist yet. And i can't jump to itself. Compute dp[i] first, then insert i.

Greedy: always jump to the biggest value in reach

Pattern confusion with Jump Game I/II, where a greedy "farthest reach" works because you only care whether (or how fast) you get there. Here every landing adds to the score. In [1, 2, 5] with k = 2, jumping straight to the biggest value 5 gives 6, but landing on 2 first gives 8. Local choices don't add up to the best total — that needs dp.

Comparing nums instead of dp in the deque

✗ while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();

✓ while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();

We are looking for the best place to jump from, which is the best score so far (dp), not the best single value. Copying Sliding Window Maximum without changing nums to dp gives wrong answers.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Constrained Subsequence Sum