#2770

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number of Jumps to Reach the Last Index

Find the maximum number of jumps to reach the last index using state transition dynamic programming efficiently in arrays.

array dynamic programming

Problem Statement

You are given a 0-indexed integer array nums and an integer target. Starting at index 0, you may jump from index i to index j if 0 <= i < j < nums.length and abs(nums[i] - nums[j]) <= target.

Your task is to determine the maximum number of jumps needed to reach the last index n - 1. If reaching the last index is impossible, return -1. The challenge emphasizes state transition dynamic programming to track jump counts efficiently.

Examples

Example 1

Input: nums = [1,3,6,4,1,2], target = 2

Output: 3

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

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

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

Solution Approach

Dynamic Programming Initialization

Create a DP array where dp[i] represents the maximum number of jumps to reach index i. Initialize dp[0] = 0 and all other indices to -1 to indicate unreachable states.

State Transition

For each index i, iterate through previous indices j < i. If abs(nums[i] - nums[j]) <= target and dp[j] != -1, update dp[i] = max(dp[i], dp[j] + 1). This captures the maximum jumps using valid transitions only.

Result Extraction

After processing all indices, dp[n-1] contains the maximum jumps to reach the last index. If dp[n-1] remains -1, return -1. This ensures correctness even when some paths cannot reach the end.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to nested iteration over indices for state transitions. Space complexity is O(n) for the DP array storing maximum jumps at each index.

What Interviewers Usually Probe

Checks if candidate recognizes state transition DP as core pattern.
Looks for clear handling of unreachable indices with -1 in DP.
Wants candidate to justify why nested iteration captures maximum jumps correctly.

Common Pitfalls or Variants

Common pitfalls

Failing to consider that some indices may never be reachable, leaving -1 incorrectly.
Using greedy jumps instead of DP, which can miss maximum jump sequences.
Forgetting to check abs(nums[i] - nums[j]) <= target for all valid previous indices.

Follow-up variants

Compute minimum jumps to reach last index instead of maximum.
Allow jumps in both directions, not just forward, with target constraint.
Optimize for large n by using segment trees or monotonic queues for DP transitions.

FAQ

What is the primary pattern for Maximum Number of Jumps to Reach the Last Index?

The problem uses state transition dynamic programming, storing the maximum jumps for each index and updating based on valid prior jumps.

Can negative numbers in nums affect the solution?

Yes, negative numbers are valid but the DP update uses abs(nums[i] - nums[j]) <= target, so only the absolute difference matters.

Is there a more efficient approach than O(n^2)?

For large n, segment trees or monotonic queues can optimize state updates, but standard DP is O(n^2).

What should be returned if the last index is unreachable?

Return -1 if no sequence of jumps can reach the last index according to the target constraint.

How does the DP approach handle multiple paths to the same index?

It records the maximum jumps among all valid previous indices, ensuring the longest sequence is captured at each state.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n - 1:
                return 0
            ans = -inf
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) <= target:
                    ans = max(ans, 1 + dfs(j))
            return ans

        n = len(nums)
        ans = dfs(0)
        return -1 if ans < 0 else ans

Continue Practicing

#2771 longest non decreasing subarray from two arrays #2786 visit array positions to maximize score #2750 ways to split array into good subarrays