2770. Maximum Jumps to Reach Last Index Solution

Q: Is Maximum Number of Jumps to Reach the Last Index easy or hard?

The problem is rated Medium because the jump condition introduces a dynamic programming state transition that is not immediately obvious. Once the dp[i] definition is established, the implementation becomes straightforward with O(n^2) complexity.

Q: Maximum Number of Jumps to Reach the Last Index Python/Java solution

Python and Java implementations typically use the DP approach with nested loops. Maintain a dp array initialized with negative infinity except dp[0] = 0, iterate through indices, and update reachable states when the absolute difference condition is satisfied. The implementation is straightforward and runs in O(n^2) time.

Q: How to solve Maximum Number of Jumps to Reach the Last Index in O(n)?

A strict O(n) solution is generally not feasible for the general constraints because every pair of indices may need to be checked to verify the value difference condition. Most accepted solutions use O(n^2) Dynamic Programming. Some optimizations can prune checks but do not guarantee linear time in the worst case.

Q: What is the best approach for Maximum Number of Jumps to Reach the Last Index?

Dynamic Programming is the most common approach. Define dp[i] as the maximum number of jumps needed to reach index i, then check all previous indices j < i where |nums[i] - nums[j]| <= target. Update dp[i] = max(dp[i], dp[j] + 1). This method runs in O(n^2) time and O(n) space and clearly models the transition between valid jumps.

Q: Is Maximum Number of Jumps to Reach the Last Index asked at Google/Amazon/Meta?

Problems involving dynamic programming on arrays and graph-style transitions appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of jump or reachability problems are especially common because they test state transitions, DP reasoning, and complexity analysis.

Q: What data structure is used in Maximum Number of Jumps to Reach the Last Index?

The main data structure is an array used as a dynamic programming table to store the best number of jumps for each index. In the BFS approach, a queue is used to process indices level by level while exploring valid forward jumps.

Q: What is the time complexity of Maximum Number of Jumps to Reach the Last Index?

The standard solution runs in O(n^2) time because each index may compare with every previous index to verify the jump condition. The space complexity is O(n) for storing the DP state or visited structure. Both the Dynamic Programming and BFS approaches share the same worst‑case complexity.

The 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.

Example 1:

Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1. 
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3.

Example 2:

Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5.

Example 3:

Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.

Constraints:

2 <= nums.length == n <= 1000
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

Approach overview

Problem Overview: You are given an integer array nums and a value target. Starting from index 0, you can jump to index j if |nums[j] - nums[i]| <= target and j > i. The goal is to reach the last index using the maximum number of valid jumps. If reaching the last index is impossible, return -1.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

Use dynamic programming to track the maximum jumps needed to reach each index. Create a dp array where dp[i] represents the maximum number of jumps required to reach index i. Initialize dp[0] = 0 and all other entries as negative infinity (unreachable). For each index i, iterate through all previous indices j < i. If |nums[i] - nums[j]| <= target and dp[j] is reachable, update dp[i] = max(dp[i], dp[j] + 1). This checks every valid transition and builds the best jump count incrementally. The approach runs in O(n²) time because every pair of indices may be checked, and uses O(n) space for the DP table.

Approach 2: Breadth-First Search (O(n²) time, O(n) space)

Model the array as a graph where each index represents a node and edges exist when the jump constraint is satisfied. Using breadth-first search, start from index 0 and explore all reachable indices. Each level of BFS corresponds to one additional jump. Instead of stopping at the first reach of the last index, continue exploring to track the maximum number of steps that still reach it. Maintain a queue of indices and a visited structure to avoid redundant processing. Since each node may check all future nodes for valid jumps, the worst‑case complexity remains O(n²) with O(n) extra space.

The core observation is that every jump moves forward in the array, which prevents cycles and allows either DP transitions or graph traversal. The constraint check |nums[j] - nums[i]| <= target determines whether an edge exists between two indices.

Recommended for interviews: The Dynamic Programming approach is typically expected. It directly models the problem as "maximum transitions to reach index i" and is easier to reason about during interviews. BFS demonstrates the graph interpretation and is useful when explaining alternative perspectives, but the DP solution usually communicates stronger algorithmic clarity.

Approach 1: Dynamic Programming Approach

This problem can be approached using dynamic programming. The idea is to maintain a dp array where dp[i] represents the maximum number of jumps required to reach the ith index. Initialize the dp array with -1, except dp[0], which should be 0 because we start from index 0.

Iterate over the array, and for each index i, iterate again to find all j such that i < j and nums[j] - nums[i] lies within the given target range. For each such j, update dp[j] to be the maximum of its current value or dp[i] + 1.

Finally, the solution will be the value at dp[n-1]. If it's still -1, return -1 as it's impossible to reach the last index.

Python

def maxJumps(nums, target):
    n = len(nums)
    dp = [-1] * n
    dp[0] = 0
    for i in range(n):
        if dp[i] == -1:
            continue
        for j in range(i + 1, n):
            if abs(nums[j] - nums[i]) <= target:
                dp[j] = max(dp[j], dp[i] + 1)
    return dp[-1]

# Example use case
nums = [1, 3, 6, 4, 1, 2]
target = 2
print(maxJumps(nums, target))

Java

public class Solution {
    public int maxJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] == -1) continue;
            for (int j = i + 1; j < n; ++j) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n-1];
    }
}

C++

#include <vector>
#include <cmath>

int maxJumps(std::vector<int>& nums, int target) {
    int n = nums.size();
    std::vector<int> dp(n, -1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[i] == -1) continue;
        for (int j = i + 1; j < n; ++j) {
            if (std::abs(nums[j] - nums[i]) <= target) {
                dp[j] = std::max(dp[j], dp[i] + 1);
            }
        }
    }
    return dp[n-1];
}

JavaScript

function maxJumps(nums, target) {
    const n = nums.length;
    const dp = new Array(n).fill(-1);
    dp[0] = 0;
    for (let i = 0; i < n; i++) {
        if (dp[i] == -1) continue;
        for (let j = i + 1; j < n; j++) {
            if (Math.abs(nums[j] - nums[i]) <= target) {
                dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }
    }
    return dp[n - 1];
}

// Example use case
console.log(maxJumps([1, 3, 6, 4, 1, 2], 2));

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

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

int main() {
    int nums[] = {1, 3, 6, 4, 1, 2};
    int size = 6;
    int target = 2;
    int result = maxJumps(nums, size, target);
    printf("Result: %d\n", result);
    return 0;
}

public class Solution {
    public int MaxJumps(int[] nums, int target) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) continue;
            for (int j = i + 1; j < n; j++) {
                if (Math.Abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.Max(dp[j], dp[i] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

This Python function uses a dynamic programming approach to calculate the maximum number of allowable jumps. It initializes a dp array to trace the maximum jumps to every index, updated for each valid j within the target range.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor

Approach 2: Breadth-First Search Approach

The problem can also be solved using Breadth-First Search (BFS) where each position in the array can be thought of as a node in a graph. From each node, you can jump to any other node that satisfies the conditions as explained in the problem.

Using BFS, we start at index 0 and explore all possible indices we can jump to, level by level, maintaining a count of the depth or number of jumps. If we reach the last index, we return the number of jumps. If all possibilities are exhausted and the last index is not reached, return -1.

Python

from collections import deque

def maxJumps(nums, target):
    n = len(nums)
    queue = deque([(0, 0)])  # pair of (index, jump_count)
    visited = [False] * n
    visited[0] = True
    while queue:
        current, jumps = queue.popleft()
        if current == n - 1:
            return jumps
        for j in range(current + 1, n):
            if not visited[j] and abs(nums[j] - nums[current]) <= target:
                visited[j] = True
                queue.append((j, jumps + 1))
    return -1

# Example use case
nums = [1, 3, 6, 4, 1, 2]
target = 2
print(maxJumps(nums, target))

Java

import java.util.*;

public class Solution {
    public int maxJumps(int[] nums, int target) {
        int n = nums.length;
        Queue<Integer> q = new LinkedList<>();
        int[] jumps = new int[n];
        Arrays.fill(jumps, -1);
        q.add(0);
        jumps[0] = 0;
        while (!q.isEmpty()) {
            int index = q.poll();
            int jumpCount = jumps[index];
            for (int j = index + 1; j < n; j++) {
                if (jumps[j] == -1 && Math.abs(nums[j] - nums[index]) <= target) {
                    jumps[j] = jumpCount + 1;
                    q.add(j);
                }
            }
        }
        return jumps[n - 1];
    }
}

C++

#include <vector>
#include <queue>
#include <cmath>

int maxJumps(std::vector<int>& nums, int target) {
    int n = nums.size();
    std::queue<std::pair<int, int>> q;
    std::vector<bool> visited(n, false);
    q.push({0, 0});
    visited[0] = true;
    while (!q.empty()) {
        auto [current, jumps] = q.front(); q.pop();
        if (current == n - 1) return jumps;
        for (int j = current + 1; j < n; ++j) {
            if (!visited[j] && std::abs(nums[j] - nums[current]) <= target) {
                visited[j] = true;
                q.push({j, jumps + 1});
            }
        }
    }
    return -1;
}

JavaScript

function maxJumps(nums, target) {
    const n = nums.length;
    const queue = [[0, 0]]; // [[index, jumps]]
    const visited = new Array(n).fill(false);
    visited[0] = true;
    let current = 0;
    while (current < queue.length) {
        const [index, jumps] = queue[current++];
        if (index === n - 1) return jumps;
        for (let j = index + 1; j < n; j++) {
            if (!visited[j] && Math.abs(nums[j] - nums[index]) <= target) {
                queue.push([j, jumps + 1]);
                visited[j] = true;
            }
        }
    }
    return -1;
}

// Example use case
console.log(maxJumps([1, 3, 6, 4, 1, 2], 2));

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

typedef struct {
    int index;
    int jumps;
} QueueNode;

int maxJumps(int* nums, int numsSize, int target) {
    QueueNode* queue = (QueueNode*)malloc(numsSize * sizeof(QueueNode));
    int front = 0, rear = 0;
    int* visited = (int*)calloc(numsSize, sizeof(int));
    queue[rear++] = (QueueNode){0, 0};
    visited[0] = 1;
    while (front < rear) {
        QueueNode node = queue[front++];
        int current = node.index, jumps = node.jumps;
        if (current == numsSize - 1) {
            free(queue);
            free(visited);
            return jumps;
        }
        for (int j = current + 1; j < numsSize; j++) {
            if (!visited[j] && abs(nums[j] - nums[current]) <= target) {
                visited[j] = 1;
                queue[rear++] = (QueueNode){j, jumps + 1};
            }
        }
    }
    free(queue);
    free(visited);
    return -1;
}

int main() {
    int nums[] = {1, 3, 6, 4, 1, 2};
    int size = 6;
    int target = 2;
    printf("Result: %d\n", maxJumps(nums, size, target));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxJumps(int[] nums, int target) {
        int n = nums.Length;
        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
        bool[] visited = new bool[n];
        queue.Enqueue(Tuple.Create(0, 0));
        visited[0] = true;
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            int current = node.Item1, jumps = node.Item2;
            if (current == n - 1) return jumps;
            for (int j = current + 1; j < n; j++) {
                if (!visited[j] && Math.Abs(nums[j] - nums[current]) <= target) {
                    visited[j] = true;
                    queue.Enqueue(Tuple.Create(j, jumps + 1));
                }
            }
        }
        return -1;
    }
}

This Python solution is similar to the C++ solution, where BFS is used. A deque from the collections module enqueues each potential jump with an acceptable condition, iterating until the last index is reached.

Complexity

Time Complexity: O(n^2) due to potential full traversal.
Space Complexity: O(n) for the queue and visited nodes list.

Try this approach in the editor

Approach 3: Memoization

For each position i, we consider to jump to position j which satisfies |nums[i] - nums[j]| leq target. Then we can jump from i to j, and continue to jump from j to the end.

Therefore, we design a function dfs(i), which represents the maximum number of jumps needed to jump to the end index starting from position i. Then the answer is dfs(0).

The calculation process of function dfs(i) is as follows:

If i = n - 1, then we have reached the end index and no jumps are required, so return 0;
Otherwise, we need to enumerate the positions j that can be jumped from position i, and calculate the maximum number of jumps needed to jump to the end index starting from j, then dfs(i) is equal to the maximum value of all dfs(j) plus 1. If there is no position j that can be jumped from i, then dfs(i) = -infty.

To avoid duplicate calculations, we can use memoization.

Time complexity O(n^2), space complexity O(n). where n is the length of array.

TypeScript

function maximumJumps(nums: number[], target: number): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (i === n - 1) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        f[i] = -(1 << 30);
        for (let j = i + 1; j < n; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= target) {
                f[i] = Math.max(f[i], 1 + dfs(j));
            }
        }
        return f[i];
    };
    const ans = dfs(0);
    return ans < 0 ? -1 : ans;
}

func maximumJumps(nums []int, target int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i == n-1 {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		f[i] = -(1 << 30)
		for j := i + 1; j < n; j++ {
			if abs(nums[i]-nums[j]) <= target {
				f[i] = max(f[i], 1+dfs(j))
			}
		}
		return f[i]
	}
	ans := dfs(0)
	if ans < 0 {
		return -1
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n^2) Space Complexity: O(n)
Breadth-First Search Approach	Time Complexity: O(n^2) due to potential full traversal. Space Complexity: O(n) for the queue and visited nodes list.
Memoization	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming	O(n²)	O(n)	General solution for maximizing jumps while tracking best result per index
Breadth-First Search	O(n²)	O(n)	Useful when modeling the array as a graph and exploring reachable indices level by level

Frequently asked questions

Is Maximum Number of Jumps to Reach the Last Index easy or hard?

The problem is rated Medium because the jump condition introduces a dynamic programming state transition that is not immediately obvious. Once the dp[i] definition is established, the implementation becomes straightforward with O(n^2) complexity.

Maximum Number of Jumps to Reach the Last Index Python/Java solution

Python and Java implementations typically use the DP approach with nested loops. Maintain a dp array initialized with negative infinity except dp[0] = 0, iterate through indices, and update reachable states when the absolute difference condition is satisfied. The implementation is straightforward and runs in O(n^2) time.

How to solve Maximum Number of Jumps to Reach the Last Index in O(n)?

A strict O(n) solution is generally not feasible for the general constraints because every pair of indices may need to be checked to verify the value difference condition. Most accepted solutions use O(n^2) Dynamic Programming. Some optimizations can prune checks but do not guarantee linear time in the worst case.

What is the best approach for Maximum Number of Jumps to Reach the Last Index?

Dynamic Programming is the most common approach. Define dp[i] as the maximum number of jumps needed to reach index i, then check all previous indices j < i where |nums[i] - nums[j]| <= target. Update dp[i] = max(dp[i], dp[j] + 1). This method runs in O(n^2) time and O(n) space and clearly models the transition between valid jumps.

Is Maximum Number of Jumps to Reach the Last Index asked at Google/Amazon/Meta?

Problems involving dynamic programming on arrays and graph-style transitions appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of jump or reachability problems are especially common because they test state transitions, DP reasoning, and complexity analysis.

What data structure is used in Maximum Number of Jumps to Reach the Last Index?

The main data structure is an array used as a dynamic programming table to store the best number of jumps for each index. In the BFS approach, a queue is used to process indices level by level while exploring valid forward jumps.

What is the time complexity of Maximum Number of Jumps to Reach the Last Index?

The standard solution runs in O(n^2) time because each index may compare with every previous index to verify the jump condition. The space complexity is O(n) for storing the DP state or visited structure. Both the Dynamic Programming and BFS approaches share the same worst‑case complexity.

Maximum Number of Jumps to Reach the Last Index solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Breadth-First Search Approach

Approach 3: Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Number of Jumps to Reach the Last Index solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Breadth-First Search Approach

Approach 3: Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems