Maximum Number of Jumps to Reach the Last Index

Maximum Number of Jumps to Reach the Last Index - Problem

You are given a 0-indexed array nums of n integers and an integer target.

You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:

0 <= i < j < n
-target <= nums[j] - nums[i] <= target

Return the maximum number of jumps you can make to reach index n - 1.

If there is no way to reach index n - 1, return -1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,5,1], target = 3

› Output: 3

💡 Note: From index 0 (value 4), we can jump to indices 1, 2, or 3. Optimal path: 0→1→2→3 gives us 3 jumps maximum.

Example 2 — Limited Jumps

$ Input: nums = [3,5,7], target = 1

› Output: 1

💡 Note: From index 0 (value 3), we can only jump to index 2 (value 7) since |7-3|=4 > target=1 is false, but we can jump to index 1 first. Path: 0→2 gives 1 jump, or 0→1→2 but |7-5|=2 > 1.

Example 3 — No Path

$ Input: nums = [1,10], target = 2

› Output: -1

💡 Note: From index 0 (value 1), we cannot reach index 1 (value 10) because |10-1| = 9 > target = 2.

Constraints

2 ≤ nums.length ≤ 1000
-10⁹ ≤ nums[i] ≤ 10⁹
1 ≤ target ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,2,5,1] with target=3

Valid Jumps

Check which positions we can jump to based on value difference

Output

Maximum jumps possible: 3

Key Takeaway

🎯 Key Insight: We want to maximize jumps, not minimize them, so we explore all valid paths using dynamic programming

Asked in

f Meta 15 G Google 12 a Amazon 8

The key insight is that we want to maximize jumps rather than minimize them, so we use dynamic programming to track the maximum number of jumps possible from each position. The optimal approach is bottom-up DP working backwards from the goal. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n²)	O(n)	Cache results of subproblems to avoid recomputation
Brute Force Recursion	O(2^n)	O(n)	Try all possible jump sequences using recursion
Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution from right to left using DP array

Memoization (Top-Down DP) — Algorithm Steps

Use recursion with memoization
Cache maximum jumps possible from each position
Return cached result if already computed
Build solution from top-down

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate maximum jumps from each position

Cache

Store result in memo table

Reuse

Return cached result if position revisited

Code -

solution.c — C

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

int memo[1000];
int memoSize;

int dfs(int* nums, int target, int pos, int n) {
    if (pos == n - 1) {
        return 0;
    }
    
    if (pos < memoSize && memo[pos] != -2) {
        return memo[pos];
    }
    
    int maxJumps = -1;
    for (int nextPos = pos + 1; nextPos < n; nextPos++) {
        if (abs(nums[nextPos] - nums[pos]) <= target) {
            int jumps = dfs(nums, target, nextPos, n);
            if (jumps != -1) {
                maxJumps = (maxJumps > 1 + jumps) ? maxJumps : 1 + jumps;
            }
        }
    }
    
    if (pos < memoSize) {
        memo[pos] = maxJumps;
    }
    return maxJumps;
}

int solution(int* nums, int numsSize, int target) {
    memoSize = numsSize;
    for (int i = 0; i < numsSize; i++) {
        memo[i] = -2;
    }
    return dfs(nums, target, 0, numsSize);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each position computed once, with up to n transitions each

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization array and recursion stack both use O(n) space

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

745 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

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler