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] <= targetReturn 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] <= 1090 <= target <= 2 * 109Problem 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.
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.
Time Complexity: O(n^2) due to the nested loop iterations.
Space Complexity: O(n) for storing the dp array.
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.
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.
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:
i = n - 1, then we have reached the end index and no jumps are required, so return 0;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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) due to the nested loop iterations. |
| Breadth-First Search Approach | Time Complexity: O(n^2) in the worst case as every index might be checked against every other index. |
| Memoization | — |
| 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 |
Leetcode Weekly contest 353 - Medium - Maximum Number of Jumps to Reach the Last Index • Prakhar Agrawal • 1,545 views views
Watch 9 more video solutions →Practice Maximum Number of Jumps to Reach the Last Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor