Skip to content

1340. Jump Game V 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)