Jump Game V - Practice Coding Problems

Jump Game V - Problem

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Input & Output

Example 1 — Basic Case

$ Input: arr = [6,4,14,6,9], d = 2

› Output: 3

💡 Note: Start at index 2 (value 14): 14→6→4, visiting 3 indices. From 14 we can jump to positions with values 6,6,9 within distance 2. From 6 we can jump to 4.

Example 2 — Limited Jumps

$ Input: arr = [3,3,3,3,3], d = 3

› Output: 1

💡 Note: All values are equal, so no valid jumps possible since we need arr[i] > arr[j]. Can only visit 1 index.

Example 3 — Blocked Path

$ Input: arr = [2,6,4], d = 1

› Output: 2

💡 Note: From index 1 (value 6), can jump to index 0 (value 2) or index 2 (value 4). Maximum path is 2 indices.

Constraints

1 ≤ arr.length ≤ 1000
1 ≤ d ≤ arr.length
1 ≤ arr[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with heights and maximum jump distance

Valid Jumps

Can only jump down to lower heights within distance d

Maximum Path

Find longest sequence of valid jumps

Key Takeaway

🎯 Key Insight: Process positions from highest to lowest value to ensure optimal substructure in dynamic programming

Asked in

f Facebook 45 G Google 38 a Amazon 32

The key insight is that this is a directed graph problem where we can only move from higher to lower values. The optimal approach uses topological sorting combined with dynamic programming, processing positions from highest to lowest value. Time: O(n × d), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Topological Sort + DP	O(n × d)	O(n)	Process nodes in topological order for optimal dynamic programming
Memoized DFS	O(n² × d)	O(n)	Cache DFS results to avoid recomputing the same subproblems
Brute Force DFS	O(d^n)	O(n)	Try all possible jumping sequences from every starting position

Topological Sort + DP — Algorithm Steps

Sort indices by their values in descending order
Process positions from highest to lowest value
For each position, find maximum path by checking all valid jumps
Use precomputed results from lower-height positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Height

Order positions from highest to lowest value

Bottom-up DP

Process each position using precomputed lower positions

Optimal Result

Find maximum across all positions

Code -

solution.c — C

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

typedef struct {
    int value;
    int index;
} IndexValue;

int compare(const void* a, const void* b) {
    IndexValue* ia = (IndexValue*)a;
    IndexValue* ib = (IndexValue*)b;
    return ib->value - ia->value;
}

int canJump(int* arr, int i, int j, int d) {
    if (abs(i - j) > d || arr[i] <= arr[j]) {
        return 0;
    }
    int start = i < j ? i : j;
    int end = i > j ? i : j;
    for (int k = start + 1; k < end; k++) {
        if (arr[k] >= arr[i]) {
            return 0;
        }
    }
    return 1;
}

int solution(int* arr, int n, int d) {
    int* dp = (int*)malloc(n * sizeof(int));
    IndexValue* sorted = (IndexValue*)malloc(n * sizeof(IndexValue));
    
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        sorted[i].value = arr[i];
        sorted[i].index = i;
    }
    
    qsort(sorted, n, sizeof(IndexValue), compare);
    
    // Process from highest to lowest
    for (int idx = 0; idx < n; idx++) {
        int i = sorted[idx].index;
        int startPos = i - d > 0 ? i - d : 0;
        int endPos = i + d < n - 1 ? i + d : n - 1;
        
        for (int j = startPos; j <= endPos; j++) {
            if (j != i && canJump(arr, i, j, d)) {
                if (1 + dp[j] > dp[i]) {
                    dp[i] = 1 + dp[j];
                }
            }
        }
    }
    
    int result = 1;
    for (int i = 0; i < n; i++) {
        if (dp[i] > result) {
            result = dp[i];
        }
    }
    
    free(dp);
    free(sorted);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Process each of n positions once, checking up to d jumps per position

✓ Linear Growth

Space Complexity

O(n)

DP array and sorted indices array both take O(n) space

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Topological Sort + DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler