Jump Game V

🎯 Problem

You are given:

• An integer array arr
• An integer d

From index i, you can jump:

• Left
• Right

But only up to distance d.

✅ Jump Conditions

You can jump from index i to index j only if:

1. Distance Condition

|i - j| <= d

2. Smaller Value Condition

arr[i] > arr[j]

3. Blocking Condition

All elements between i and j must also be smaller than arr[i].

If a taller or equal element appears:

🚫 Jump becomes blocked.

🎯 Goal

We can start from ANY index.

Return:

Maximum number of indices we can visit.

🧠 Main Observation

For every index:

We want to know:

"What is the maximum path length starting from this index?"

This is a DP problem.

✅ DP Meaning

dp[i]

means:

Maximum indices we can visit starting from index i.

🔥 Main Idea

From every index:

Try all valid jumps:

• Left
• Right

Take maximum answer among all paths.

✅ Why DFS?

Each index explores:

• Smaller neighboring values
• Further possible jumps

This naturally forms:

DFS + Memoization

✅ Memoization Benefit

If answer for an index is already calculated:

No need to calculate again.

Store result in:

dp[i]

📌 DFS Formula

For every valid next index:

answer = 1 + dfs(nextIndex)

Take maximum among all choices.

⚠️ Important Blocking Rule

While moving left or right:

If we encounter:

arr[next] >= arr[current]

Immediately stop exploring further.

Because jump gets blocked.

🪜 Example

Input

arr = [6,4,14,6,8,13,9,7,10,6,12]
d = 2

📌 Index Representation

Index:
0  1  2  3  4  5  6  7  8  9  10

Value:
6  4 14  6  8 13  9  7 10  6 12

🔍 Start From Index 10

Current value:

12

Possible jumps within distance 2:

• Index 9 → value 6 ✅
• Index 8 → value 10 ✅

Both are smaller than 12.

So we explore both.

🔍 DFS at Index 8

Current value:

10

Possible jumps:

• Index 7 → value 7 ✅
• Index 6 → value 9 ✅

Explore both.

🔍 DFS at Index 6

Current value:

9

Possible jumps:

• Index 7 → value 7 ✅

Index 5:

13

Blocked ❌

Because:

13 > 9

Cannot move further left.

🔍 DFS at Index 7

Current value:

7

Left:

9 > 7

Blocked ❌

Right:

10 > 7

Blocked ❌

No valid jumps.

So:

dp[7] = 1

🔄 Backtracking

Now:

dp[6] = 1 + dp[7]
       = 2

Similarly:

dp[8] = 1 + max(dp[6], dp[7])
       = 3

✅ Final Path

Best path:

10 → 8 → 6 → 7

Visited indices:

4

Answer:

4

✅ Java Solution

class Main {

    static int[] dp;

    public static int dfs(int[] arr, int d, int index) {

        // Already calculated
        if (dp[index] != 0) {
            return dp[index];
        }

        int max = 1;

        // Move Right
        for (int i = index + 1; i <= Math.min(index + d, arr.length - 1); i++) {

            // Blocked
            if (arr[i] >= arr[index]) {
                break;
            }

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

        // Move Left
        for (int i = index - 1; i >= Math.max(index - d, 0); i--) {

            // Blocked
            if (arr[i] >= arr[index]) {
                break;
            }

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

        return dp[index] = max;
    }

    public static int maxJumps(int[] arr, int d) {

        int n = arr.length;

        dp = new int[n];

        int answer = 1;

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

        return answer;
    }

    public static void main(String[] args) {

        int[] arr = {6,4,14,6,8,13,9,7,10,6,12};

        int d = 2;

        System.out.println(
            maxJumps(arr, d)
        );
    }
}

⏱️ Time Complexity

O(N × d)

Because each index explores at most:

• d positions left
• d positions right

💾 Space Complexity

O(N)

Used for:

• DP array
• Recursion stack

🚀 Final Takeaway

Key Learnings:

• DFS explores all paths
• Memoization avoids repeated work
• Blocking condition is very important
• Stop immediately when taller/equal element appears

This combination of:

DFS + DP

gives optimized solution efficiently.