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
-10⁹ <= nums[i] <= 10⁹
0 <= target <= 2 * 10⁹

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.

Solution 2: Dynamic Programming

Thinking

Enumerating every jump sequence is exponential. The array length reaches $1000$, and a legal step to the next index is always tried first, so the search has depth $n$. The most jumps from index $i$ depend only on later indexes. Let $f[i]$ be that number, with $f[n-1]=0$, and scan landing indexes from the right, updating with $1+f[j]$ when the absolute difference is at most $target$. A still-negative $f[0]$ means the end is unreachable, so the answer is $-1$.

Let $f[i]$ be the maximum number of jumps from index $i$ to the end. Set $f[n-1]=0$ and every earlier entry to $-\infty$. For $i$ from $n-2$ down to $0$, enumerate a landing index $j$ ($i < j < n$). If $

nums[i]-nums[j]

\leq target$, update $f[i]$ with $1+f[j]$. If $f[0]$ is still negative, the end cannot be reached and the answer is $-1$; otherwise the answer is $f[0]$.

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;
    }
}


// Solution 2
class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, -(1 << 30));
        f[n - 1] = 0;
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (Math.abs(nums[i] - nums[j]) <= target) {
                    f[i] = Math.max(f[i], 1 + f[j]);
                }
            }
        }
        return f[0] < 0 ? -1 : f[0];
    }
}

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;
    }
};


// Solution 2
class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(n, -(1 << 30));
        f[n - 1] = 0;
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (abs(nums[i] - nums[j]) <= target) {
                    f[i] = max(f[i], 1 + f[j]);
                }
            }
        }
        return f[0] < 0 ? -1 : f[0];
    }
};

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



# Solution 2
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [-inf] * n
        f[-1] = 0
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) <= target:
                    f[i] = max(f[i], 1 + f[j])
        return -1 if f[0] < 0 else f[0]

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
}


// Solution 2
func maximumJumps(nums []int, target int) int {
	n := len(nums)
	f := make([]int, n)
	for i := range f {
		f[i] = -(1 << 30)
	}
	f[n-1] = 0
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if abs(nums[i]-nums[j]) <= target {
				f[i] = max(f[i], 1+f[j])
			}
		}
	}
	if f[0] < 0 {
		return -1
	}
	return f[0]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

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;
}



// Solution 2
function maximumJumps(nums: number[], target: number): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(-(1 << 30));
    f[n - 1] = 0;
    for (let i = n - 2; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= target) {
                f[i] = Math.max(f[i], 1 + f[j]);
            }
        }
    }
    return f[0] < 0 ? -1 : f[0];
}

impl Solution {
    pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut f = vec![-1; n];

        fn dfs(i: usize, nums: &Vec<i32>, target: i32, f: &mut Vec<i32>) -> i32 {
            if i == nums.len() - 1 {
                return 0;
            }
            if f[i] != -1 {
                return f[i];
            }
            f[i] = -(1 << 30);
            for j in i + 1..nums.len() {
                if (nums[i] - nums[j]).abs() <= target {
                    f[i] = f[i].max(1 + dfs(j, nums, target, f));
                }
            }
            f[i]
        }

        let ans = dfs(0, &nums, target, &mut f);
        if ans < 0 { -1 } else { ans }
    }
}



// Solution 2
impl Solution {
    pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut f = vec![-(1 << 30); n];
        f[n - 1] = 0;
        for i in (0..n - 1).rev() {
            for j in i + 1..n {
                if (nums[i] - nums[j]).abs() <= target {
                    f[i] = f[i].max(1 + f[j]);
                }
            }
        }
        if f[0] < 0 {
            -1
        } else {
            f[0]
        }
    }
}

2770 - Maximum Number of Jumps to Reach the Last Index

2770. Maximum Number of Jumps to Reach the Last Index

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

2770. Maximum Number of Jumps to Reach the Last Index

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions