# Jump Game V
**Difficulty:** HARD
[External](https://leetcode.com/problems/jump-game-v)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-v
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
Given an array of integers `arr` and an integer `d`. In one step you can jump from index `i` to index:

* `i + x` where: `i + x < arr.length` and ` 0 < x <= d`.
* `i - x` where: `i - x >= 0` and ` 0 < x <= d`.

In addition, you can only jump from index `i` to index `j` if `arr[i] > arr[j]` and `arr[i] > arr[k]` for all indices `k` between `i` and `j` (More formally `min(i, j) < k < max(i, j)`).

You can choose any index of the array and start jumping. Return _the maximum number of indices_ you can visit.

Notice that you can not jump outside of the array at any time.

**Example 1:**

![](https://assets.glich.co/dsa/jump-game-v/image0.jpeg) 

**Input:** arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
**Output:** 4
**Explanation:** You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

**Example 2:**

**Input:** arr = [3,3,3,3,3], d = 3
**Output:** 1
**Explanation:** You can start at any index. You always cannot jump to any index.

**Example 3:**

**Input:** arr = [7,6,5,4,3,2,1], d = 1
**Output:** 7
**Explanation:** Start at index 0. You can visit all the indicies. 

**Constraints:**

* `1 <= arr.length <= 1000`
* `1 <= arr[i] <= 105`
* `1 <= d <= arr.length`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem statement into a recursive solution. We define a function that explores all possible valid jump sequences starting from a given index. For each index in the array, we initiate this exploration and find the length of the longest path. The final answer is the maximum length found across all possible starting indices.
**Time:** O(d^n) in the worst case. The recursion tree can be very deep and wide, with each node having up to 2d branches. This leads to an exponential number of calls, many of which are for the same subproblems. · **Space:** O(n), where n is the number of elements in the array. This is for the recursion stack depth in the worst case (e.g., a strictly decreasing array).
**Pros:** Simple to conceptualize and implement.; Follows the problem description directly.
**Cons:** Extremely inefficient due to massive re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The core of this method is a recursive function, let's call it `dfs(i)`, which calculates the maximum number of indices you can visit starting from index `i`. This function works as follows:

1.  The base case for the recursion is a path of length 1, which is just the starting index `i` itself.
2.  From index `i`, we explore all possible jumps to the right within the distance `d`. A jump to index `j` is valid only if `arr[i]` is strictly greater than `arr[j]` and all elements between `i` and `j`. If we encounter an element `arr[k]` (with `k` between `i` and `j`) that is greater than or equal to `arr[i]`, we cannot jump to `j` or any index beyond `k` in that direction.
3.  For each valid jump to an index `j`, we recursively call `dfs(j)` to find the length of the longest path from `j`. We then update our current maximum path length from `i` with `1 + dfs(j)`.
4.  We repeat the same process for all possible jumps to the left.
5.  The main part of the program iterates through every index `i` from `0` to `n-1`, using each as a potential starting point, and returns the overall maximum path length found.

This method explores the entire search space, but it's highly inefficient because it recalculates the longest path for the same index multiple times.

```java
class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int maxJumps = 0;
        for (int i = 0; i < n; i++) {
            maxJumps = Math.max(maxJumps, dfs(i, arr, d));
        }
        return maxJumps;
    }

    private int dfs(int i, int[] arr, int d) {
        int n = arr.length;
        int max = 1;

        // Jump to the right
        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) {
                break; // Cannot jump over a taller or equal bar
            }
            // Valid jump to j
            max = Math.max(max, 1 + dfs(j, arr, d));
        }

        // Jump to the left
        for (int j = i - 1; j >= Math.max(i - d, 0); j--) {
            if (arr[j] >= arr[i]) {
                break; // Cannot jump over a taller or equal bar
            }
            // Valid jump to j
            max = Math.max(max, 1 + dfs(j, arr, d));
        }
        return max;
    }
}
```
### Algorithm
- Define a recursive function `dfs(i)` that returns the maximum number of indices that can be visited starting from index `i`.
- Inside `dfs(i)`, initialize a result `maxVisits = 1` (for the current index).
- Iterate to the right from `i+1` to `min(i+d, n-1)`. For each index `j`, check if the jump is valid. A jump is valid if `arr[j] < arr[i]` and all intermediate elements are also smaller than `arr[i]`. If an element `arr[k]` with `k > i` is found such that `arr[k] >= arr[i]`, we cannot jump to `k` or any index beyond it, so we stop searching in this direction.
- If a jump to `j` is valid, recursively call `dfs(j)` and update `maxVisits = max(maxVisits, 1 + dfs(j))`.
- Similarly, iterate to the left from `i-1` down to `max(0, i-d)` and perform the same logic.
- Return `maxVisits`.
- The main function iterates through all possible starting indices `i` from `0` to `n-1`, calls `dfs(i)`, and keeps track of the maximum result found.

## Top-Down Dynamic Programming with Memoization
This approach significantly improves upon the brute-force method by using memoization, a key technique in dynamic programming. We observe that the recursive function `dfs(i)` is called multiple times with the same index `i`, leading to redundant computations. By storing the result of `dfs(i)` the first time it's computed and reusing it for subsequent calls, we can reduce the time complexity from exponential to polynomial. This is also known as top-down dynamic programming.
**Time:** O(n * d). Each state `dfs(i)` for `i` from 0 to `n-1` is computed exactly once. The work done within each call is proportional to `d` because of the two loops exploring up to `d` indices in each direction. · **Space:** O(n), where n is the array length. This space is used for the memoization array `memo` and the recursion stack.
**Pros:** Highly efficient and sufficient to pass the given constraints.; Often intuitive to derive from a brute-force recursive solution.; Asymptotically faster than a sorting-based bottom-up approach for this problem.
**Cons:** Relies on recursion, which can have overhead and stack depth limitations in some environments (though not an issue for n=1000).; Slightly more complex than the brute-force approach due to the memoization table.
### Explanation
We augment the recursive solution with a memoization table, typically an array `memo`, to store the results of subproblems. `memo[i]` will hold the maximum number of indices that can be visited starting from index `i`.

The algorithm is as follows:
1.  Initialize a `memo` array of the same size as `arr` with a sentinel value (e.g., 0) to indicate that the result for that index has not been computed yet.
2.  Modify the `dfs(i)` function. At the beginning of the function, check if `memo[i]` already contains a computed result. If it does, return that value immediately.
3.  If `memo[i]` has not been computed, proceed with the same logic as the brute-force approach: calculate the maximum path length by exploring valid jumps to the left and right and making recursive calls.
4.  Once the result for `i` is computed, store it in `memo[i]` before returning.
5.  The main loop still iterates through all indices `i` as starting points, calling the memoized `dfs(i)` and tracking the overall maximum.

This ensures that the longest path for each index is calculated exactly once.

```java
class Solution {
    int[] memo;
    int[] arr;
    int d;
    int n;

    public int maxJumps(int[] arr, int d) {
        this.n = arr.length;
        this.arr = arr;
        this.d = d;
        this.memo = new int[n];
        
        int maxJumps = 0;
        for (int i = 0; i < n; i++) {
            maxJumps = Math.max(maxJumps, dfs(i));
        }
        return maxJumps;
    }

    private int dfs(int i) {
        if (memo[i] != 0) {
            return memo[i];
        }

        int res = 1;
        // Jump to the right
        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }

        // Jump to the left
        for (int j = i - 1; j >= Math.max(0, i - d); j--) {
            if (arr[j] >= arr[i]) {
                break;
            }
            res = Math.max(res, 1 + dfs(j));
        }
        
        memo[i] = res;
        return res;
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `n`, initialized to 0. `memo[i]` will store the result of the longest path starting from `i`.
- Define a recursive function `dfs(i)`.
- Inside `dfs(i)`, first check if `memo[i]` is non-zero. If so, a result has been computed, so return `memo[i]`.
- Initialize `res = 1`.
- Explore jumps to the right (from `i+1` to `min(i+d, n-1)`). Stop if a blocking element (`arr[j] >= arr[i]`) is found. For each valid jump to `j`, update `res = max(res, 1 + dfs(j))`.
- Explore jumps to the left (from `i-1` to `max(0, i-d)`) similarly.
- Store the final result in `memo[i] = res` and return it.
- The main function calls `dfs(i)` for all `i` from `0` to `n-1` and returns the maximum value obtained.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int d;
private
  int[] arr;
private
  Integer[] f;
public
  int maxJumps(int[] arr, int d) {
    n = arr.length;
    this.d = d;
    this.arr = arr;
    f = new Integer[n];
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, dfs(i));
    }
    return ans;
  }
private
  int dfs(int i) {
    if (f[i] != null) {
      return f[i];
    }
    int ans = 1;
    for (int j = i - 1; j >= 0; --j) {
      if (i - j > d || arr[j] >= arr[i]) {
        break;
      }
      ans = Math.max(ans, 1 + dfs(j));
    }
    for (int j = i + 1; j < n; ++j) {
      if (j - i > d || arr[j] >= arr[i]) {
        break;
      }
      ans = Math.max(ans, 1 + dfs(j));
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxJumps(vector<int> &arr, int d) {
    int n = arr.size();
    int f[n];
    memset(f, 0, sizeof(f));
    function<int(int)> dfs = [&](int i) -> int {
      if (f[i]) {
        return f[i];
      }
      int ans = 1;
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > d || arr[j] >= arr[i]) {
          break;
        }
        ans = max(ans, 1 + dfs(j));
      }
      for (int j = i + 1; j < n; ++j) {
        if (j - i > d || arr[j] >= arr[i]) {
          break;
        }
        ans = max(ans, 1 + dfs(j));
      }
      return f[i] = ans;
    };
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, dfs(i));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int: @ cache def dfs(i): ans = 1 for j in range(i - 1, - 1, - 1): if i - j > d or arr[j] >= arr[i]: break ans = max(ans, 1 + dfs(j)) for j in range(i + 1, n): if j - i > d or arr[j] >= arr[i]: break ans = max(ans, 1 + dfs(j)) return ans n = len(arr) return max(dfs(i) for i in range(n))

```