1340. Jump Game V LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1340. Jump Game V LeetCode Solution with the best time and space complexity. The solution to Jump Game V problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Jump Game V solution in C++
Jump Game V solution in Java
Jump Game V solution in Python
Additional Resources

1340. Jump Game V LeetCode Solution image

Problem Statement of Jump Game V

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 = 0 and 0 < x 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] <= 105
1 <= d <= arr.length

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1340. Jump Game V LeetCode Solution in C++

class Solution {
 public:
  int maxJumps(vector<int>& arr, int d) {
    const int n = arr.size();
    // dp[i] := the maximum jumps starting from arr[i]
    vector<int> dp(n, 1);
    // a dcreasing stack that stores indices
    stack<int> stack;

    for (int i = 0; i <= n; ++i) {
      while (!stack.empty() && (i == n || arr[stack.top()] < arr[i])) {
        vector<int> indices{stack.top()};
        stack.pop();
        while (!stack.empty() && arr[stack.top()] == arr[indices[0]])
          indices.push_back(stack.top()), stack.pop();
        for (const int j : indices) {
          if (i < n && i - j <= d)
            // Can jump from i to j.
            dp[i] = max(dp[i], dp[j] + 1);
          if (!stack.empty() && j - stack.top() <= d)
            // Can jump from stack[-1] to j.
            dp[stack.top()] = max(dp[stack.top()], dp[j] + 1);
        }
      }
      stack.push(i);
    }

    return ranges::max(dp);
  }
};
/* code provided by PROGIEZ */

1340. Jump Game V LeetCode Solution in Java

class Solution {
  public int maxJumps(int[] arr, int d) {
    final int n = arr.length;
    // dp[i] := the maximum jumps starting from arr[i]
    int[] dp = new int[n];
    // a dcreasing stack that stores indices
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i <= n; ++i) {
      while (!stack.isEmpty() && (i == n || arr[stack.peek()] < arr[i])) {
        List<Integer> indices = new ArrayList<>(List.of(stack.pop()));
        while (!stack.isEmpty() && arr[stack.peek()] == arr[indices.get(0)])
          indices.add(stack.pop());
        for (final int j : indices) {
          if (i < n && i - j <= d)
            // Can jump from i to j.
            dp[i] = Math.max(dp[i], dp[j] + 1);
          if (!stack.isEmpty() && j - stack.peek() <= d)
            // Can jump from stack.peek() to j
            dp[stack.peek()] = Math.max(dp[stack.peek()], dp[j] + 1);
        }
      }
      stack.push(i);
    }

    return Arrays.stream(dp).max().getAsInt() + 1;
  }
}
// code provided by PROGIEZ

1340. Jump Game V LeetCode Solution in Python

class Solution:
  def maxJumps(self, arr: list[int], d: int) -> int:
    n = len(arr)
    # dp[i] := the maximum jumps starting from arr[i]
    dp = [1] * n
    # a dcreasing stack that stores indices
    stack = []

    for i in range(n + 1):
      while stack and (i == n or arr[stack[-1]] < arr[i]):
        indices = [stack.pop()]
        while stack and arr[stack[-1]] == arr[indices[0]]:
          indices.append(stack.pop())
        for j in indices:
          if i < n and i - j <= d:
            # Can jump from i to j.
            dp[i] = max(dp[i], dp[j] + 1)
          if stack and j - stack[-1] <= d:
            # Can jump from stack[-1] to j
            dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
      stack.append(i)

    return max(dp)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents