Jump Game VI - Practice Coding Problems

Jump Game VI - Problem

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.

Input & Output

Example 1 — Basic Jump Game

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

› Output: 7

💡 Note: You can jump from index 0 → 3 → 5. Score = 1 + 4 + 3 = 8. But optimal path is 0 → 1 → 3 → 5 with score 1 + (-1) + 4 + 3 = 7.

Example 2 — Large Jumps

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

› Output: 17

💡 Note: Optimal path: 0 → 3 → 5. Score = 10 + 4 + 3 = 17. With k=3, we can jump up to 3 steps, so from index 0 we can reach indices 1, 2, or 3.

Example 3 — Single Element

$ Input: nums = [1], k = 1

› Output: 1

💡 Note: Only one element in array, so the score is nums[0] = 1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array with values and maximum jump distance k

Process

Find path from start to end maximizing sum of visited values

Output

Maximum possible score

Key Takeaway

🎯 Key Insight: Use monotonic deque to efficiently track the best position to jump from in the current window

Asked in

G Google 45 F Facebook 38 A Amazon 32 M Microsoft 28

The key insight is to use dynamic programming where dp[i] represents the maximum score to reach index i. The optimal approach uses a monotonic deque to efficiently find the best previous position in O(1) time. Time: O(n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n × k)	O(n)	Build solution iteratively from left to right
Monotonic Deque Optimization	O(n)	O(k)	Use deque to maintain sliding window maximum efficiently
Dynamic Programming with Memoization	O(n × k)	O(n)	Cache recursive results to avoid recomputation
Recursive Brute Force	O(k^n)	O(n)	Try all possible jump sequences recursively

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize dp array with dp[0] = nums[0]
For each position i, check all positions j where j is within k steps behind
Set dp[i] = max(dp[j] + nums[i]) for valid j
Return dp[n-1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0] = nums[0], others to -infinity

Fill DP

For each position, find max from reachable previous positions

Result

dp[n-1] contains the maximum score

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int max_func(int a, int b) {
    return (a > b) ? a : b;
}

int max_func_three(int a, int b) {
    return (a > b) ? a : b;
}

int solution(int* nums, int numsSize, int k) {
    if (numsSize == 1) return nums[0];
    
    int* dp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = INT_MIN;
    }
    dp[0] = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        int start = (i - k > 0) ? i - k : 0;
        for (int j = start; j < i; j++) {
            if (dp[j] != INT_MIN) {
                dp[i] = max_func(dp[i], dp[j] + nums[i]);
            }
        }
    }
    
    int result = dp[numsSize - 1];
    free(dp);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For each of n positions, we check up to k previous positions

✓ Linear Growth

Space Complexity

O(n)

DP array stores maximum score for each of n positions

⚡ Linearithmic Space

67.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler