Jump Game V

Jump Game V

1. What is this problem about?

The Jump Game V interview question asks you to find the maximum number of indices you can visit in a single trip. You start at any index. From index i, you can jump to any j such that:

1. 0 <= j < n
2. 0 < |i - j| <= d (maximum jump distance $d$).
3. arr[i] > arr[k] for all $k$ between $i$ and $j$ (inclusive of $j$). This means you can only jump "down" onto smaller bars, and you cannot jump "over" any bar that is taller than or equal to your current starting bar.

2. Why is this asked in interviews?

Google uses the Jump Game V coding problem to test your ability to use Dynamic Programming with a specific ordering. Since you can only jump to smaller values, the "dependency graph" is a Directed Acyclic Graph (DAG). It evaluation if you can identify that you should process smaller values before larger ones, or use memoization to solve the problem recursively.

3. Algorithmic pattern used

This problem follows the Memoized Depth-First Search pattern.

1. State: solve(i) is the maximum jumps starting from index i.
2. Recursive Logic:
   • From i, look at all $j$ within range $[i-d, i+d]$.
   • As you move left/right from $i$, stop the search if you hit a bar $\geq arr[i]$.
   • For every valid $j$, solve(i) = max(solve(i), 1 + solve(j)).
3. Base Case: If no jumps are possible, solve(i) = 1.
4. Global Max: The answer is the maximum solve(i) across all $i \in [0, n-1]$.

4. Example explanation

arr = [3, 3, 3, 3, 3], $d=3$.

• From any index, you can't jump because every neighbor is equal to you (violates Rule 3: arr[i] > arr[k]).
• Max indices visited: 1. arr = [14, 13, 5, 2], $d=2$.
• From 14: can jump to 13 or 5.
• From 13: can jump to 5 or 2.
• From 5: can jump to 2. The path 14 -> 13 -> 5 -> 2 visits 4 indices.

5. Common mistakes candidates make

• Sorting indices: Not realizing that sorting the indices by their values allows for a simple iterative DP solution.
• Ignoring Rule 3: Trying to jump over a taller bar to reach a smaller one further away.
• Recursive TLE: Forgetting the @cache or memo table, which turns an $O(N \cdot D)$ problem into an exponential one.

6. Interview preparation tip

When a jump rule only allows moving to "strictly smaller" or "strictly larger" values, the graph is a DAG. This is a huge hint that you can solve the problem using Dynamic Programming or Topological Sort. Practice this Tree interview pattern logic for complex sequences.