Welcome to Subscribe On Youtube

2770. Maximum Number of Jumps to Reach the Last Index

Description

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] <= target

Return 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] <= 109
  • 0 <= target <= 2 * 109

Solutions

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.

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:

  • If $i = n - 1$, then we have reached the end index and no jumps are required, so return $0$;
  • Otherwise, we need to enumerate the positions $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.

  • class Solution {
        private Integer[] f;
        private int[] nums;
        private int n;
        private int target;
    
        public int maximumJumps(int[] nums, int target) {
            n = nums.length;
            this.target = target;
            this.nums = nums;
            f = new Integer[n];
            int ans = dfs(0);
            return ans < 0 ? -1 : ans;
        }
    
        private int dfs(int i) {
            if (i == n - 1) {
                return 0;
            }
            if (f[i] != null) {
                return f[i];
            }
            int ans = -(1 << 30);
            for (int j = i + 1; j < n; ++j) {
                if (Math.abs(nums[i] - nums[j]) <= target) {
                    ans = Math.max(ans, 1 + dfs(j));
                }
            }
            return f[i] = ans;
        }
    }
    
  • class Solution {
    public:
        int maximumJumps(vector<int>& nums, int target) {
            int n = nums.size();
            int f[n];
            memset(f, -1, sizeof(f));
            function<int(int)> dfs = [&](int i) {
                if (i == n - 1) {
                    return 0;
                }
                if (f[i] != -1) {
                    return f[i];
                }
                f[i] = -(1 << 30);
                for (int j = i + 1; j < n; ++j) {
                    if (abs(nums[i] - nums[j]) <= target) {
                        f[i] = max(f[i], 1 + dfs(j));
                    }
                }
                return f[i];
            };
            int ans = dfs(0);
            return ans < 0 ? -1 : ans;
        }
    };
    
  • 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
    
    
  • func maximumJumps(nums []int, target int) int {
    	n := len(nums)
    	f := make([]int, n)
    	for i := range f {
    		f[i] = -1
    	}
    	var dfs func(int) int
    	dfs = func(i int) int {
    		if i == n-1 {
    			return 0
    		}
    		if f[i] != -1 {
    			return f[i]
    		}
    		f[i] = -(1 << 30)
    		for j := i + 1; j < n; j++ {
    			if abs(nums[i]-nums[j]) <= target {
    				f[i] = max(f[i], 1+dfs(j))
    			}
    		}
    		return f[i]
    	}
    	ans := dfs(0)
    	if ans < 0 {
    		return -1
    	}
    	return ans
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • function maximumJumps(nums: number[], target: number): number {
        const n = nums.length;
        const f: number[] = Array(n).fill(-1);
        const dfs = (i: number): number => {
            if (i === n - 1) {
                return 0;
            }
            if (f[i] !== -1) {
                return f[i];
            }
            f[i] = -(1 << 30);
            for (let j = i + 1; j < n; ++j) {
                if (Math.abs(nums[i] - nums[j]) <= target) {
                    f[i] = Math.max(f[i], 1 + dfs(j));
                }
            }
            return f[i];
        };
        const ans = dfs(0);
        return ans < 0 ? -1 : ans;
    }
    
    

All Problems

All Solutions