Skip to main content
Talentd

Maximum Number of Jumps to Reach the Last Index - Solution & Explanation

MediumArrayDynamic Programming24 min readAsked at: Amazon, Meta
Practice this problem

Problem Statement

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
  • -109 <= nums[i] <= 109
  • 0 <= target <= 2 * 109

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.

This C program defines a function maxJumps that takes an array of integers nums, its size numsSize, and a target. It initializes a dynamic programming array dp to track the maximum jumps to each index. By iterating through and updating dp[j] as dp[i] + 1 when the condition is met, it aims to reach the last index with maximum jumps. dp[n-1] is returned, and -1 is returned if it's not reachable.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to the nested loop iterations.
Space Complexity: O(n) for storing the dp array.

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.

This C solution employs a queue to implement the BFS algorithm. Each node in the queue contains an index of the array and the number of jumps made to reach this index. We start from index 0, exploring each possible jump to a valid subsequent index until reaching the last index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) in the worst case as every index might be checked against every other index.
Space Complexity: O(n) as the queue could grow to a maximum size equaling the number of elements.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2) due to the nested loop iterations.
Space Complexity: O(n) for storing the dp array.

Breadth-First Search Approach

Time Complexity: O(n^2) in the worst case as every index might be checked against every other index.
Space Complexity: O(n) as the queue could grow to a maximum size equaling the number of elements.

Memoization—

Detailed Complexity Analysis

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

Video Solution

Maximum Number of Jumps to Reach the Last Index | Simple Intuition | Leetcode 2770 | MIK • codestorywithMIK • 6,106 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Number of Jumps to Reach the Last Index with our built-in code editor and test cases.

Practice on FleetCode
Previous

Frog Jump

Next

Jump Game II