Maximum Number of Jumps to Reach the Last Index

Medium
1638.

Maximum Number of Jumps to Reach the Last Index

Maximum Number of Jumps to Reach the Last Index is a medium coding problem on arrays and dynamic programming, asked in Amazon interviews.

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^9
  • 0 <= target <= 2 * 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var maximumJumps = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^9
  • 0 <= target <= 2 * 10^9

Hints for Maximum Number of Jumps to Reach the Last Index

  1. Hint 1

    Jumps only go forward, so the indices form a DAG and you want its longest path from 0 to n - 1.

  2. Hint 2

    Let dp[j] be the most jumps that reach index j (or unreachable). Then dp[j] = max(dp[i] + 1) over earlier reachable i with |nums[j] - nums[i]| <= target.

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

  1. Set dp[0] = 0 and dp[j] = -1 (unreachable) for j > 0.
  2. For each j from 1 to n - 1, for each i < j with dp[i] >= 0 and |nums[j] - nums[i]| <= target, set dp[j] = max(dp[j], dp[i] + 1).
  3. 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 be 2·10^9 and overflow a 32-bit int — use 64-bit arithmetic.
  • Never extend from an unreachable index: -1 + 1 = 0 would 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