LeetCode 1340 - Jump Game V

LeetCode Problem 1340

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Sorting

Solution

Here is a comprehensive solution guide for LeetCode 1340 following your requested format.

Problem Understanding

The problem presents an array arr of integers and a maximum jump distance d. You can jump from an index i to another index j within d steps to the left or right, but only if the height at the destination arr[j] is strictly lower than the current height arr[i], and all elements in between are strictly lower than arr[i]. The goal is to determine the maximum number of indices that can be visited starting from any index.

The input consists of an array with up to 1000 elements, each between 1 and 100,000. The jump distance d is at most the length of the array. This size suggests that an $O(n^2)$ approach may barely fit within time limits, but anything worse may time out.

Important edge cases include arrays where all elements are equal (no jumps possible), strictly increasing or decreasing sequences (jumping is highly restricted or fully sequential), and d = 1 (minimal jump range).

Approaches

The brute-force approach is to attempt a Depth-First Search (DFS) from each index, exploring every valid jump recursively and keeping track of the maximum path length. This guarantees correctness because it explores all possible paths. However, it is highly inefficient, with time complexity $O(n \cdot 2^d)$ in the worst case, because for each index, we can attempt multiple recursive jumps.

The optimal approach leverages Dynamic Programming with Memoization. The key insight is that the maximum jumps starting from an index i can be determined recursively, and once computed, it can be cached. By sorting indices by height and only allowing jumps from higher to lower elements, we ensure correctness and avoid redundant computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * 2^d)	O(n)	DFS from each index, explores all paths
Optimal	O(n * d)	O(n)	DFS with memoization avoids recomputation, considers jumps only up to d distance

Algorithm Walkthrough

1. Initialize a memoization array dp of size n with all values set to -1. dp[i] will store the maximum jumps starting from index i.
2. Define a recursive function dfs(i) that computes the maximum jumps starting from index i.
3. For each index j to the right of i within distance d, stop if arr[j] >= arr[i]; otherwise, recursively compute dfs(j) and update the maximum.
4. Repeat similarly for each index j to the left of i within distance d.
5. Store the result in dp[i] and return it.
6. Iterate over all indices, invoking dfs(i) for each, and track the maximum result among all starting indices.

Why it works: The memoization ensures each index’s maximum jump is computed once. By restricting jumps to strictly lower heights and considering all intermediate elements via the loop, the algorithm respects the problem’s constraints. The recursive DFS guarantees that all valid sequences are evaluated.

Python Solution

from typing import List

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [-1] * n
        
        def dfs(i: int) -> int:
            if dp[i] != -1:
                return dp[i]
            max_jump = 1  # the minimum jump count is 1 (itself)
            # explore right
            for j in range(i + 1, min(i + d + 1, n)):
                if arr[j] >= arr[i]:
                    break
                max_jump = max(max_jump, 1 + dfs(j))
            # explore left
            for j in range(i - 1, max(i - d - 1, -1), -1):
                if arr[j] >= arr[i]:
                    break
                max_jump = max(max_jump, 1 + dfs(j))
            dp[i] = max_jump
            return dp[i]
        
        return max(dfs(i) for i in range(n))

The Python implementation follows the algorithm step by step. It uses memoization to avoid recomputation, iterates within distance d in both directions, and breaks the loop when the jump condition is violated. The max function ensures we always store the best path.

Go Solution

func maxJumps(arr []int, d int) int {
    n := len(arr)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = -1
    }
    
    var dfs func(int) int
    dfs = func(i int) int {
        if dp[i] != -1 {
            return dp[i]
        }
        maxJump := 1
        for j := i + 1; j < min(i+d+1, n); j++ {
            if arr[j] >= arr[i] {
                break
            }
            maxJump = max(maxJump, 1+dfs(j))
        }
        for j := i - 1; j >= max(i-d, 0); j-- {
            if arr[j] >= arr[i] {
                break
            }
            maxJump = max(maxJump, 1+dfs(j))
        }
        dp[i] = maxJump
        return dp[i]
    }
    
    result := 0
    for i := 0; i < n; i++ {
        result = max(result, dfs(i))
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go solution mirrors the Python version. It uses slices for memoization, recursive closures for DFS, and helper functions for min and max. The main differences are Go syntax and range handling, especially for slices.

Worked Examples

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

Index	DFS path	dp value
10	10 -> 8 -> 6 -> 7	4
0	0 -> 1	2
2	2 -> 3	2

Maximum = 4

Example 2: arr = [3,3,3,3,3], d = 3

All elements are equal, no jumps possible. Each dp[i] = 1, max = 1

Example 3: arr = [7,6,5,4,3,2,1], d = 1

Each element can jump to the next lower element. Starting from index 0, path length = 7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * d)	Each index is computed once via DFS, exploring at most d neighbors
Space	O(n)	Memoization array dp and recursion stack up to n

Memoization prevents redundant computations, making the approach efficient for the given constraints.

Test Cases

# Provided examples
assert Solution().maxJumps([6,4,14,6,8,13,9,7,10,6,12], 2) == 4  # complex jumps
assert Solution().maxJumps([3,3,3,3,3], 3) == 1  # no jumps possible
assert Solution().maxJumps([7,6,5,4,3,2,1], 1) == 7  # fully decreasing sequence

# Edge tests
assert Solution().maxJumps([1], 1) == 1  # single element
assert Solution().maxJumps([1,2,3,4,5], 2) == 1  # strictly increasing, no jumps
assert Solution().maxJumps([5,4,3,2,1], 5) == 5  # strictly decreasing, maximum jumps
assert Solution().maxJumps([1,3,2,4,1], 2) == 3  # mix of increasing and decreasing

Test	Why
[6,4,14,6,8,13,9,7,10,6,12], 2	Complex path with breaks due to taller intermediate values
[3,3,3,3,3], 3	No possible jumps
[7,6,5,4,3,2,1], 1	Full sequential jumps
[1]	Minimal array
[1,2,3,4,5], 2	Increasing sequence prevents jumps
[5,4,3,2,1], 5	Decreasing sequence allows maximal jumps
[1,3,2,4,1], 2	Mixed sequence tests left and right jumps

Edge Cases

Single element array: When arr has length 1, no jumps are possible. The implementation correctly returns 1, as each index counts as a valid visited index.

Equal heights array