Jump Game V: DP on Sorted Values

You are given an array of integers arr and an integer d. You stand on some index i and can jump to index j if all three conditions hold: the distance |i - j| is at most d, arr[i] is strictly greater than arr[j], and every value between positions i and j is also strictly less than arr[i]. You want to find the maximum number of indices you can visit starting from any index.

This is LeetCode 1340: Jump Game V, a hard problem that combines dynamic programming with a clever processing order. The key is figuring out when to compute each dp value so that all dependencies are already resolved.

Why this problem matters

Jump Game V is a clean example of a problem where the order you fill your DP table matters more than the recurrence itself. The recurrence is simple: dp[i] = 1 + max(dp[j]) for all reachable j from i. But if you try to fill the table left-to-right or right-to-left, you run into circular dependency issues. Index 3 might depend on index 5, which depends on index 4, which depends on index 3. A naive ordering does not work.

The insight that breaks this open is that you can only jump to shorter bars. That means dependencies always point from taller values to shorter values. If you process indices from shortest bar to tallest, every value you need is already computed by the time you need it. This is the same principle behind topological sort on a DAG, except here the DAG is implicit in the value ordering.

This pattern of "process items in dependency order" shows up across many DP problems. Longest Increasing Subsequence uses the same idea when you iterate left-to-right (smaller indices are already processed). Here, the ordering is by value rather than by position, which is what makes the problem tricky to spot at first.

The approach

The core observation: you can only jump from a taller bar to a shorter bar. So if you process all indices sorted by their arr values from smallest to largest, every index you could jump to from index i has already been processed. Its dp value is ready to use.

For each index i (processed in ascending value order), scan left up to d positions. If arr[j] is strictly less than arr[i], index j is reachable and you can use dp[j]. But if arr[j] is greater than or equal to arr[i], that bar blocks your path. You cannot see past it, so stop scanning in that direction. Do the same scan to the right.

def max_jumps(arr, d):
    n = len(arr)
    dp = [1] * n

    for idx in sorted(range(n), key=lambda i: arr[i]):
        for j in range(idx - 1, max(-1, idx - d - 1), -1):
            if arr[j] >= arr[idx]:
                break
            dp[idx] = max(dp[idx], 1 + dp[j])
        for j in range(idx + 1, min(n, idx + d + 1)):
            if arr[j] >= arr[idx]:
                break
            dp[idx] = max(dp[idx], 1 + dp[j])

    return max(dp)

Walking through the example

Let's trace through arr = [6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12] with d = 2. We process indices from smallest value to largest, building up dp values along the way.

The final dp array is [2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 4]. The maximum is dp[10] = 4, corresponding to the path starting at index 10 (value 12), jumping to index 8 (value 10), then to index 6 (value 9), and finally to index 7 (value 7).

Notice how processing by ascending value guarantees that when we compute dp[10], the value dp[8] = 3 is already available. Index 8 was processed earlier because arr[8] = 10 is less than arr[10] = 12.

You can also solve this with memoization (top-down DP), which avoids the explicit sorting step:

def max_jumps(arr, d):
    n = len(arr)
    memo = {}

    def dp(i):
        if i in memo:
            return memo[i]
        best = 1
        for j in range(i - 1, max(-1, i - d - 1), -1):
            if arr[j] >= arr[i]:
                break
            best = max(best, 1 + dp(j))
        for j in range(i + 1, min(n, i + d + 1)):
            if arr[j] >= arr[i]:
                break
            best = max(best, 1 + dp(j))
        memo[i] = best
        return best

    return max(dp(i) for i in range(n))

Complexity analysis

Time: O(n * d). Sorting takes O(n log n). For each of the n indices, you scan at most d positions left and d positions right. The scanning dominates when d is large, giving O(n * d) total. Since d can be at most n, worst case is O(n^2).

Space: O(n). The dp array (or memoization dictionary) stores one value per index. The sorted index list also uses O(n).

Edge cases to watch for

• d = 1: you can only jump to immediately adjacent indices that are strictly shorter. The problem reduces to a simpler local comparison.
• All values identical: no jumps are possible anywhere because you need strictly shorter bars. Every dp value is 1.
• Strictly descending array like [5, 4, 3, 2, 1] with large d: from index 0 you can reach every other index. The answer is n.
• Strictly ascending array like [1, 2, 3, 4, 5] with large d: from index n-1 you can reach every other index. Same answer, n.
• Single element: the answer is 1. You are already standing on the only index.
• Large d with blocking bars: even if d is large, a tall bar in the middle blocks further scanning. Do not forget the break when you encounter a bar with value greater than or equal to arr[i].

The building blocks

1. Value-ordered DP processing

The pattern of sorting items by some property (here, the array value) so that DP dependencies are resolved before they are needed. This is equivalent to computing DP in topological order on the implicit dependency graph. You see this in:

• Longest Increasing Subsequence: process left-to-right, which naturally orders by position. But binary search optimizations rely on value ordering.
• Course Schedule / topological sort: process nodes whose prerequisites are already completed.
• Matrix problems with obstacle constraints: fill DP cells in an order that respects which cells depend on which.

2. Bounded scanning with early termination

The pattern of scanning left and right from an index up to a fixed distance, but stopping early when a blocking condition is met. The break on encountering a bar that is at least as tall as the current one is the key correctness detail. Without it, you would incorrectly count jumps over tall obstacles.

From understanding to recall

The algorithm has three moving parts: sort indices by value, scan left and right within distance d with a blocking check, and take the maximum dp value plus one. Each piece is simple on its own, but assembling them correctly under pressure requires practice.

The processing order is the part most people forget. You know you need DP, you know the recurrence, but when you sit down to code it, you reach for a left-to-right loop and realize the dependencies are wrong. The "sort by value, process smallest first" trick is what makes everything click. Drilling it with spaced repetition turns it from an insight you vaguely remember into a tool you reach for automatically.

Related posts

• Jump Game - The foundational jump game problem with greedy approach
• Jump Game II - Finding minimum jumps with BFS-like greedy
• Longest Increasing Subsequence - Another DP problem where processing order matters

CodeBricks breaks Jump Game V into its value-ordered DP and bounded-scan building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a "process in dependency order" problem shows up in your interview, you do not think about it. You just write it.