Leetcode 2770: Maximum Number of Jumps to Reach the Last Index
Given an array nums of integers and a target value, find the maximum number of jumps needed to reach the last index. A jump from index i to index j is valid if j > i and the difference nums[j] - nums[i] lies within the range [-target, target]. If it is impossible to reach the last index, return -1.
Problem
Approach
Steps
Complexity
Input: The input consists of an array nums of size n and an integer target.
Example: Input: nums = [2, 5, 9, 6, 2, 3], target = 3
Constraints:
• 2 <= nums.length == n <= 1000
• -10^9 <= nums[i] <= 10^9
• 0 <= target <= 2 * 10^9
Output: The output is an integer representing the maximum number of jumps to reach the last index, or -1 if it is not possible.
Example: Output: 2 for nums = [2, 5, 9, 6, 2, 3], target = 3
Constraints:
• Output should be -1 if no valid jumping sequence exists.
Goal: Calculate the maximum number of valid jumps to reach the last index of nums.
Steps:
• Use dynamic programming to calculate the maximum jumps starting from index 0.
• For each index i, check all valid jumps to indices j > i where nums[j] - nums[i] lies within [-target, target].
• Memoize results to optimize repeated calculations.
Goal: Ensure the solution works efficiently given the constraints.
Steps:
• 2 <= nums.length == n <= 1000
• -10^9 <= nums[i] <= 10^9
• 0 <= target <= 2 * 10^9
Assumptions:
• All input values are valid and within the given constraints.
• The nums array is not empty, and target is a non-negative integer.
• Input: Input: nums = [2, 5, 9, 6, 2, 3], target = 3
• Explanation: Jump from index 0 to index 2, then from index 2 to index 5. The total number of jumps is 2.
• Input: Input: nums = [10, 15, 20, 25], target = 1
• Explanation: It is impossible to reach the last index, so the output is -1.
Approach: The problem can be solved using dynamic programming with memoization to explore all valid jumping paths efficiently.
Observations:
• Each index can potentially jump to multiple future indices based on the target constraint.
• Dynamic programming is suitable to optimize repeated subproblems.
• Memoize the maximum jumps from each index to avoid redundant calculations.
Steps:
• Define a recursive function dp(idx) to compute the maximum jumps starting from index idx.
• For each idx, iterate over all j > idx to find valid jumps where nums[j] - nums[idx] lies within [-target, target].
• Memoize the results for each index to avoid recomputation.
• Return the maximum jumps for dp(0), or -1 if no valid sequence exists.
Empty Inputs:
• Not applicable, as nums always contains at least two elements.
Large Inputs:
• Test with nums of size 1000 and large target values to ensure efficiency.
Special Values:
• Test cases with nums having repeated values and small target values.
Constraints:
• Ensure correctness for edge cases like nums = [1, 2], target = 0.
int target, n;
vector<int> memo, nums;
int dp(int idx) {
if(idx == n - 1) return 0;
if(memo[idx] != INT_MIN) return memo[idx];
int ans = INT_MIN;
for(int i = idx + 1; i < n; i++) {
if(abs(nums[i] - nums[idx]) <= target) {
ans = max(ans, dp(i) + 1);
}
}
// cout << idx << " " << ans << "\n";
return memo[idx] = ans;
}
int maximumJumps(vector<int>& nums, int target) {
n = nums.size();
this->target = target;
this->nums = nums;
memo.resize(n, INT_MIN);
int ans = dp(0);
return ans <= 0? -1: ans;
}
1 : Variable Declaration
int target, n;
Declare the integer variables `target` to store the target value and `n` to store the number of elements in `nums`.
2 : Variable Declaration
vector<int> memo, nums;
Declare a vector `nums` to store the input numbers and a vector `memo` to store intermediate results for memoization.
3 : Base Case
int dp(int idx) {
Define the function `dp` that takes an index `idx` and returns the maximum jumps possible from that index.
4 : Base Case Check
if(idx == n - 1) return 0;
Check if we are at the last index; if so, return 0 because no further jumps are possible.
5 : Memoization Check
if(memo[idx] != INT_MIN) return memo[idx];
Check if the result for the current index is already computed (i.e., not `INT_MIN`). If so, return the stored result from `memo`.
6 : Initialization
int ans = INT_MIN;
Initialize the variable `ans` to `INT_MIN` to track the maximum number of jumps from the current index.
7 : Loop Through Elements
for(int i = idx + 1; i < n; i++) {
Start a loop from the next index (`idx + 1`) to the end of the list to explore potential valid jumps.
8 : Condition Check
if(abs(nums[i] - nums[idx]) <= target) {
Check if the absolute difference between the current element and the element at index `idx` is less than or equal to the target value.
9 : Recursive Call
ans = max(ans, dp(i) + 1);
If the condition is satisfied, recursively call `dp(i)` to find the maximum jumps from index `i`, and add 1 for the current jump. Update `ans` with the maximum value.
10 : Memoization
return memo[idx] = ans;
Store the computed value of `ans` in `memo[idx]` for future use and return the value.
11 : Initialization
int maximumJumps(vector<int>& nums, int target) {
Define the `maximumJumps` function and pass `nums` and `target` as parameters.
12 : Variable Assignment
n = nums.size();
Assign the size of the `nums` vector to `n`.
13 : Variable Assignment
this->target = target;
Assign the `target` parameter to the class-level `target` variable.
14 : Variable Assignment
this->nums = nums;
Assign the input `nums` vector to the class-level `nums` vector.
15 : Initialization
memo.resize(n, INT_MIN);
Resize the `memo` vector to the size of `n`, initializing all values to `INT_MIN` to indicate uncomputed values.
16 : Call DP Function
int ans = dp(0);
Call the `dp` function starting from index 0 and store the result in `ans`.
17 : Return Statement
return ans <= 0? -1: ans;
Return `-1` if `ans` is less than or equal to 0, indicating no valid jumps. Otherwise, return the computed number of jumps.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: For each index, up to n iterations are required to check all valid jumps.
Best Case: O(n)
Worst Case: O(n)
Description: Space is used for memoization of size n.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus