Maximum Number of Jumps to Reach the Last Index — Solution
Maximum Number of Jumps to Reach the Last Index solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Jumps to Reach the Last Index is a medium coding problem on arrays and dynamic programming, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of n integers and an integer target. You start at index 0. In one jump you may move from index i to any index j with i < j < n as long as -target <= nums[j] - nums[i] <= target.
Return the maximum number of jumps that takes you from index 0 to index n - 1, or -1 if index n - 1 cannot be reached.
Example 1
Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: 0 → 1 → 3 → 5: values 1, 3, 4, 2, each step changes by at most 2.
Example 2
Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: Every adjacent step is allowed: 0 → 1 → 2 → 3 → 4 → 5.
Example 3
Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: No jump keeps the value the same.
Constraints
2 <= nums.length <= 1000-10^9 <= nums[i] <= 10^90 <= target <= 2 * 10^9
Hints for Maximum Number of Jumps to Reach the Last Index
Hint 1
Jumps only go forward, so the indices form a DAG and you want its longest path from
0ton - 1.Hint 2
Let
dp[j]be the most jumps that reach indexj(or unreachable). Thendp[j] = max(dp[i] + 1)over earlier reachableiwith|nums[j] - nums[i]| <= target.Hint 3
Differences reach
2·10^9, beyond a 32-bit int: compute them in 64 bits.
How to solve Maximum Number of Jumps to Reach the Last Index
Forward-only jumps make this a longest-path problem in a DAG ordered by index, which a simple quadratic DP solves.
Approach
- Set
dp[0] = 0anddp[j] = -1(unreachable) forj > 0. - For each
jfrom 1 ton - 1, for eachi < jwithdp[i] >= 0and|nums[j] - nums[i]| <= target, setdp[j] = max(dp[j], dp[i] + 1). - Return
dp[n - 1].
Why it works
Every path to j ends with a jump from some earlier i, and the rest of it is a path to i; using the longest path to each i maximises the total. Processing indices in increasing order means each dp[i] is final before it is used.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
nums[j] - nums[i]can be2·10^9and overflow a 32-bit int — use 64-bit arithmetic.- Never extend from an unreachable index:
-1 + 1 = 0would wrongly mark it reachable. - This is the maximum number of jumps, not the minimum — BFS does not apply.
Reference solution
Python
from typing import List
def maximumJumps(nums: List[int], target: int) -> int:
n = len(nums)
dp = [-1] * n
dp[0] = 0
for j in range(1, n):
vj = nums[j]
best = -1
for i in range(j):
if dp[i] >= 0 and dp[i] + 1 > best and abs(vj - nums[i]) <= target:
best = dp[i] + 1
dp[j] = best
return dp[n - 1]Java
public static int maximumJumps(int[] nums, int target) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (dp[i] >= 0 && Math.abs((long) nums[j] - nums[i]) <= target) dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}C++
int maximumJumps(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(n, -1);
dp[0] = 0;
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
long long d = (long long)nums[j] - nums[i];
if (d < 0) d = -d;
if (dp[i] >= 0 && d <= target) dp[j] = max(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}JavaScript
var maximumJumps = function(nums, target) {
var n = nums.length, dp = new Array(n).fill(-1);
dp[0] = 0;
for (var j = 1; j < n; j++) {
for (var i = 0; i < j; i++) {
if (dp[i] >= 0 && dp[i] + 1 > dp[j] && Math.abs(nums[j] - nums[i]) <= target) dp[j] = dp[i] + 1;
}
}
return dp[n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming