2770. Maximum Number of Jumps to Reach the Last Index

Time: O(n²)

Space: O(n)

Intuition

This is a longest-path problem in a DAG. Define dp[j] as the maximum number of jumps needed to reach index j. Because we can only jump from i to j when |nums[j] - nums[i]| ≤ target and i < j, the graph is acyclic and we can fill dp left to right.

Algorithm

1Initialise dp[] with -1 (unreachable); set dp[0] = 0.
2For each j from 1 to n-1:
3 For each i from 0 to j-1:
4 If dp[i] != -1 and |nums[j] - nums[i]| <= target:
5 dp[j] = max(dp[j], dp[i] + 1).
6Return dp[n-1] (-1 means last index is unreachable).

Example Walkthrough

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

1.dp = [-1,-1,-1,-1,-1,-1], dp[0]=0.
2.j=1: |3-1|=2 ≤ 2 from i=0 → dp[1]=1.
3.j=2: |6-3|=3 > 2 (i=1 skip); |6-1|=5 > 2 (i=0 skip) → dp[2]=-1.
4.j=3: |4-3|=1 ≤ 2 from i=1 → dp[3]=2.
5.j=4: |1-3|=2 ≤ 2 from i=1 → dp[4]=2; |1-4|=3 > 2 skip.
6.j=5: |2-1|=1 ≤ 2 from i=4 → dp[5]=3; |2-4|=2 ≤ 2 from i=3 → dp[5]=max(3,3)=3.
7.Answer: dp[5] = 3.

Output: 3

Common Pitfalls

•Initialise dp with -1, not 0 — a 0 at an unreachable index would incorrectly allow jumps from it.
•The condition is |nums[j] - nums[i]| <= target (absolute value); jumping is allowed in both increasing and decreasing value directions.
•Return -1 if dp[n-1] remains -1 — the last index may be unreachable.

2770.cs

// Approach: DP where dp[j] = max jumps to reach index j from index 0.
// For each j, scan all i < j: if dp[i] != -1 and |nums[j] - nums[i]| <= target, update dp[j] = max(dp[j], dp[i] + 1).
// dp[0] = 0 (start); unreachable indices stay -1. Answer is dp[n-1].
// Time: O(n²) Space: O(n)

public class Solution
{
    public int MaximumJumps(int[] nums, int target)
    {
        int n = nums.Length;
        // dp[i] := the maximum number of jumps to reach i from 0
        int[] dp = new int[n];
        Array.Fill(dp, -1);
        dp[0] = 0;

        for (int j = 1; j < n; ++j)
        {
            for (int i = 0; i < j; ++i)
            {
                if (dp[i] != -1 && Math.Abs(nums[j] - nums[i]) <= target)
                    dp[j] = Math.Max(dp[j], dp[i] + 1);
            }
        }

        return dp[n - 1];
    }
}

Was this solution helpful?