Jump Game V

Hard

#1245Time: 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.

Patterns

Dynamic Programming

Algorithms

Sorting

Data structures

Array

Prompt

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:

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] <= 10⁵
1 <= d <= arr.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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.
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.
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.
Once the result for i is computed, store it in memo[i] before returning.
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.

1class Solution {2    int[] memo;3    int[] arr;4    int d;5    int n;6 7    public int maxJumps(int[] arr, int d) {8        this.n = arr.length;9        this.arr = arr;10        this.d = d;11        this.memo = new int[n];12        13        int maxJumps = 0;14        for (int i = 0; i < n; i++) {15            maxJumps = Math.max(maxJumps, dfs(i));16        }17        return maxJumps;18    }19 20    private int dfs(int i) {21        if (memo[i] != 0) {22            return memo[i];23        }24 25        int res = 1;26        // Jump to the right27        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {28            if (arr[j] >= arr[i]) {29                break;30            }31            res = Math.max(res, 1 + dfs(j));32        }33 34        // Jump to the left35        for (int j = i - 1; j >= Math.max(0, i - d); j--) {36            if (arr[j] >= arr[i]) {37                break;38            }39            res = Math.max(res, 1 + dfs(j));40        }41        42        memo[i] = res;43        return res;44    }45}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

The base case for the recursion is a path of length 1, which is just the starting index i itself.
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.
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).
We repeat the same process for all possible jumps to the left.
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.

1class Solution {2    public int maxJumps(int[] arr, int d) {3        int n = arr.length;4        int maxJumps = 0;5        for (int i = 0; i < n; i++) {6            maxJumps = Math.max(maxJumps, dfs(i, arr, d));7        }8        return maxJumps;9    }10 11    private int dfs(int i, int[] arr, int d) {12        int n = arr.length;13        int max = 1;14 15        // Jump to the right16        for (int j = i + 1; j <= Math.min(i + d, n - 1); j++) {17            if (arr[j] >= arr[i]) {18                break; // Cannot jump over a taller or equal bar19            }20            // Valid jump to j21            max = Math.max(max, 1 + dfs(j, arr, d));22        }23 24        // Jump to the left25        for (int j = i - 1; j >= Math.max(i - d, 0); j--) {26            if (arr[j] >= arr[i]) {27                break; // Cannot jump over a taller or equal bar28            }29            // Valid jump to j30            max = Math.max(max, 1 + dfs(j, arr, d));31        }32        return max;33    }34}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int n;4private5  int d;6private7  int[] arr;8private9  Integer[] f;10public11  int maxJumps(int[] arr, int d) {12    n = arr.length;13    this.d = d;14    this.arr = arr;15    f = new Integer[n];16    int ans = 1;17    for (int i = 0; i < n; ++i) {18      ans = Math.max(ans, dfs(i));19    }20    return ans;21  }22private23  int dfs(int i) {24    if (f[i] != null) {25      return f[i];26    }27    int ans = 1;28    for (int j = i - 1; j >= 0; --j) {29      if (i - j > d || arr[j] >= arr[i]) {30        break;31      }32      ans = Math.max(ans, 1 + dfs(j));33    }34    for (int j = i + 1; j < n; ++j) {35      if (j - i > d || arr[j] >= arr[i]) {36        break;37      }38      ans = Math.max(ans, 1 + dfs(j));39    }40    return f[i] = ans;41  }42}

1class Solution {2public:3  int maxJumps(vector<int> &arr, int d) {4    int n = arr.size();5    int f[n];6    memset(f, 0, sizeof(f));7    function<int(int)> dfs = [&](int i) -> int {8      if (f[i]) {9        return f[i];10      }11      int ans = 1;12      for (int j = i - 1; j >= 0; --j) {13        if (i - j > d || arr[j] >= arr[i]) {14          break;15        }16        ans = max(ans, 1 + dfs(j));17      }18      for (int j = i + 1; j < n; ++j) {19        if (j - i > d || arr[j] >= arr[i]) {20          break;21        }22        ans = max(ans, 1 + dfs(j));23      }24      return f[i] = ans;25    };26    int ans = 1;27    for (int i = 0; i < n; ++i) {28      ans = max(ans, dfs(i));29    }30    return ans;31  }32};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem