Leetcode QOTD:- 1340. Jump Game V

How to Think About This Problem

As we need to find the maximum number of indices we can visit by jumping left or right.

But there are conditions:

• We can jump only up to distance d
• We can jump only to a smaller value
• If a bigger/equal value comes in between, movement stops

So from every index, we want to know:
“What is the maximum path I can create starting from here?”

That is a classic DFS + DP (memoization) pattern.

Why DFS?

At every index:

• we try all valid left jumps
• we try all valid right jumps
• each jump again asks the same question:

“From this new index, how far can I go?”

This becomes a recursive exploration problem, so DFS fits naturally.

Why DP (Memoization)?

Without DP:

• same index gets recalculated many times
• recursion becomes very slow

Example:

• index 5 may be reached from multiple paths
• its answer will always remain same

So we store:
dp[i] = maximum jumps possible starting from index i

This avoids repeated work.

How This Approach Was Reached

1. We notice every index can independently act as a starting point.
2. From one index, we recursively explore all valid moves.
3. Same subproblems repeat → use memoization.
4. We need maximum path length → DFS returning best answer makes sense.

So final approach becomes:

• DFS for exploration
• DP for optimization

Logic

1. Create a dp[] array where:

• dp[i] stores max jumps possible starting from index i

1. Start DFS from every index because answer can start anywhere.

2. In DFS:

• initialize best = 1
• minimum answer is the current index itself

1. Move right up to distance d:

• if a bigger/equal element appears, stop (break)
• otherwise recursively calculate jumps

1. Move left similarly:

• stop when blocked by bigger/equal value

1. Update:
   best = max(best, 1 + dfs(nextIndex))

2. Store result in dp[i] and return it.

3. Final answer is the maximum value obtained from all starting indices.
   

class Solution {
    int[] dp;

    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        dp = new int[n];

        int ans = 1;

        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dfs(i, arr, d));
        }

        return ans;
    }

    private int dfs(int i, int[] arr, int d) {
        if (dp[i] != 0)
            return dp[i];

        int best = 1;

        for (int nxt = i + 1; nxt <= Math.min(arr.length - 1, i + d); nxt++) {
            if (arr[nxt] >= arr[i])
                break;

            best = Math.max(best, 1 + dfs(nxt, arr, d));
        }

        for (int nxt = i - 1; nxt >= Math.max(0, i - d); nxt--) {
            if (arr[nxt] >= arr[i])
                break;

            best = Math.max(best, 1 + dfs(nxt, arr, d));
        }

        return dp[i] = best;
    }
}

Comments

[Andy Nian]

DFS combined with DP works well for this problem, but make sure your base conditions are solid when using memoization. A small bug can cause issues. To really master this type of problem, visit prachub.com. Their question bank includes real follow-up questions on DFS edge cases, which is better than searching through random threads.