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: 2

💡 Note: From index 0 (value 4), we can jump to indices 1, 2, or 3. However, from index 2 we cannot reach index 3 since |1-5|=4 > target=3. The optimal path is 0→1→3, giving us 2 jumps maximum.

Example 2 — Limited Jumps

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

› Output: -1

💡 Note: From index 0 (value 3), we cannot jump to index 1 since |5-3|=2 > target=1, and we cannot jump to index 2 since |7-3|=4 > target=1. Therefore, it's impossible to reach the end.

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

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

✓ Bottom-Up Dynamic Programming

⏱️ Time: O(n²) Space: O(n)

Start from the last index and work backwards, computing the maximum jumps possible from each position. This avoids recursion and builds the solution iteratively.

Brute Force Recursion

⏱️ Time: O(2^n) Space: O(n)

For each position, recursively try all valid next positions and return the maximum jumps possible. This explores every possible path from start to end.

Memoization (Top-Down DP)

⏱️ Time: O(n²) Space: O(n)

Same recursive approach but store results in a memo table to avoid computing the same position multiple times. This eliminates redundant calculations.

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize DP array with dp[n-1] = 0
For each position from right to left
Check all valid forward jumps
Store maximum jumps possible from current position

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[n-1] = 0 (base case)

Fill DP

Work backwards, compute max jumps for each position

Result

dp[0] contains maximum jumps from start

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int target) {
    int* dp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = -1;
    }
    dp[numsSize - 1] = 0;
    
    for (int i = numsSize - 2; i >= 0; i--) {
        for (int j = i + 1; j < numsSize; j++) {
            if (abs(nums[j] - nums[i]) <= target && dp[j] != -1) {
                if (dp[i] == -1 || 1 + dp[j] > dp[i]) {
                    dp[i] = 1 + dp[j];
                }
            }
        }
    }
    
    int result = dp[0];
    free(dp);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    
    // Find the opening bracket
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++; // Skip '['
    
    // Parse numbers
    while (*ptr && *ptr != ']' && numsSize < 1000) {
        // Skip whitespace
        while (*ptr == ' ' || *ptr == '\t') ptr++;
        
        if (*ptr == ',' || *ptr == ']') {
            ptr++;
            continue;
        }
        
        // Parse number (handle negative)
        int num = 0;
        int negative = 0;
        if (*ptr == '-') {
            negative = 1;
            ptr++;
        }
        
        while (*ptr >= '0' && *ptr <= '9') {
            num = num * 10 + (*ptr - '0');
            ptr++;
        }
        
        if (negative) num = -num;
        nums[numsSize++] = num;
        
        // Skip to next number or end
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n times, inner loop up to n times each

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores one value per position

⚡ 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

Maximum Number of Jumps to Reach the Last Index - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler