1340. Jump Game V

Array
Dynamic Programming
DFS
Memoization

TIME

O(n * d)

SPACE

O(n)

Intuition

Think of each index as a node. From an index, we can move only to lower values, and a jump direction is blocked as soon as we meet an equal or higher value.

Because every jump strictly decreases the array value, there is no cycle. That makes the problem a longest path problem on a directed acyclic graph, which can be solved with DFS and memoization.

Approach

Define dfs(i) as the maximum number of indices that can be visited when starting from index i.
Initialize the answer for i as 1, counting index i itself.
Scan to the right for at most d positions:
- stop if the next value is greater than or equal to arr[i]
- otherwise update the best answer with 1 + dfs(next_index)
Do the same scan to the left.
Memoize each dfs(i) result so every index is solved once.
Return the maximum dfs(i) over all starting indices.

Complexity

Time: O(n * d), each index scans at most d positions in both directions once
Space: O(n), for memoization and recursion stack

Edge Cases

All values equal -> no valid jump, answer is 1
Strictly decreasing with d = 1 -> can visit all indices from the first index
Single element -> answer is 1
A taller or equal value inside the jump range blocks all farther indices in that direction

Code

from functools import lru_cache
from typing import List


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        """
        1340. Jump Game V
        Time: O(n * d)
        Space: O(n)
        """
        n = len(arr)

        @lru_cache(None)
        def dfs(index: int) -> int:
            best = 1

            for next_index in range(index + 1, min(n, index + d + 1)):
                if arr[next_index] >= arr[index]:
                    break
                best = max(best, 1 + dfs(next_index))

            for next_index in range(index - 1, max(-1, index - d - 1), -1):
                if arr[next_index] >= arr[index]:
                    break
                best = max(best, 1 + dfs(next_index))

            return best

        return max(dfs(index) for index in range(n))

/**
 * 1340. Jump Game V
 * Time: O(n * d)
 * Space: O(n)
 */
class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int[] memo = new int[n];
        int answer = 1;

        for (int index = 0; index < n; index++) {
            answer = Math.max(answer, dfs(index, arr, d, memo));
        }

        return answer;
    }

    private int dfs(int index, int[] arr, int d, int[] memo) {
        if (memo[index] != 0) {
            return memo[index];
        }

        int n = arr.length;
        int best = 1;

        for (int nextIndex = index + 1; nextIndex < n && nextIndex <= index + d; nextIndex++) {
            if (arr[nextIndex] >= arr[index]) {
                break;
            }
            best = Math.max(best, 1 + dfs(nextIndex, arr, d, memo));
        }

        for (int nextIndex = index - 1; nextIndex >= 0 && nextIndex >= index - d; nextIndex--) {
            if (arr[nextIndex] >= arr[index]) {
                break;
            }
            best = Math.max(best, 1 + dfs(nextIndex, arr, d, memo));
        }

        memo[index] = best;
        return best;
    }
}