Jump Game V - Solution & Explanation

Q: Is Jump Game V easy or hard?

Jump Game V is classified as Hard because it combines constrained traversal with dynamic programming. The challenge is recognizing overlapping subproblems and preventing redundant exploration using memoization or ordered DP processing.

Q: How to solve Jump Game V in O(n*d)?

Use DFS with memoization. For each index i, attempt jumps up to distance d to the left and right while the destination height is strictly smaller. Stop when encountering an equal or larger value. Store results in a dp array so each index is computed once, leading to O(n*d) total work.

Q: What is the best approach for Jump Game V?

The most common solution uses depth-first search with memoized dynamic programming. From each index, explore valid jumps left and right within distance d while the next value is smaller. Memoization stores the maximum jumps starting from each index, giving an overall time complexity of O(n*d) and space complexity of O(n).

Q: Is Jump Game V asked at Google/Amazon/Meta?

Jump Game style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test dynamic programming, graph traversal, and state transitions. Variants such as Jump Game I, II, IV, and V are commonly used to evaluate problem‑solving depth.

Q: What data structure is used in Jump Game V?

The main structure is a dynamic programming array that stores the maximum reachable indices from each position. The DFS approach also uses recursion to traverse possible jumps, effectively treating the array as a directed graph where edges represent valid moves.

Q: What is the time complexity of Jump Game V?

The optimal DFS with memoization solution runs in O(n*d) time because each index explores at most d positions in both directions once. Space complexity is O(n) for the memoization array and recursion stack. A sorting-based DP approach runs in O(n log n + n*d) due to sorting the indices by height.

Q: Jump Game V Python or Java solution approach?

Both Python and Java implementations typically use DFS with memoization. Define a recursive function dfs(i) that returns the maximum jumps starting from index i, cache results in a dp array, and iterate up to distance d in both directions while maintaining the height constraint.

HardArray Dynamic Programming Sorting18 min readAsked at: Amazon, Google

Practice this problem

Problem Statement

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10⁵
1 <= d <= arr.length

Approach Overview

Problem Overview: You are given an array arr where each value represents height. From index i, you can jump left or right up to d positions, but only to a strictly smaller value and you cannot jump over a taller or equal element. The task is to compute the maximum number of indices you can visit starting from any index.

Approach 1: Dynamic Programming with Depth‑First Search (DFS) (Time: O(n*d), Space: O(n))

This approach treats the array like a directed graph where edges represent valid jumps. For each index i, run a DFS that explores up to d steps left and right until hitting a boundary or a value greater than or equal to arr[i]. Use memoization so each index stores the maximum jumps possible starting there. During DFS, compute 1 + dfs(nextIndex) and keep the maximum. The memo table avoids recomputation, turning what would be exponential exploration into linear dynamic programming. This approach is intuitive and directly models the constraints of the problem.

Approach 2: Sorting with Dynamic Programming (Time: O(n log n + n*d), Space: O(n))

Instead of exploring recursively, process indices in increasing order of their heights. Sorting ensures that when you process an index, all potential jump destinations (which must have smaller heights) are already computed. For each index, scan left and right up to distance d while values remain smaller. Update dp[i] = max(dp[i], 1 + dp[j]) for every valid jump target j. Sorting eliminates recursion and guarantees that dependencies are resolved beforehand, making the dynamic programming transition straightforward.

Recommended for interviews: The memoized DFS approach is typically expected. It clearly shows the problem as graph traversal combined with dynamic programming. Mentioning the sorted DP optimization demonstrates deeper understanding and familiarity with alternative strategies involving arrays and sorting. Start with DFS + memoization for clarity, then discuss the ordered DP idea if asked about optimizations.

Approach 1: Dynamic Programming with Depth-First Search (DFS)

Approach: We use a combination of dynamic programming and depth-first search (DFS) to solve this problem effectively.

We maintain a DP array where dp[i] represents the maximum number of indices we can visit starting from index i. To fill this DP array, we perform DFS considering all possible valid jumps.

The DFS function checks all positions index – x (to the left) and index + x (to the right) from each position i where the jump is valid, i.e., the height requirement is satisfied. The result for each index is stored in the DP array to avoid recomputation and speed up the process.

The solution uses a recursive DFS approach where each index is traversed, and we check all indices reachable within distance d, both to the left and right. Using a DP array, we store results for these indices to avoid redundant computation.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * d), where n is the length of the array, and d is the distance constraint. Each index is visited at most once due to memoization.

Space Complexity: O(n), for the DP array used in the solution.

Try this approach in the editor →

Approach 2: Sorting with Dynamic Programming

Approach: In this approach, we preprocess the indices based on the heights in the array, then apply dynamic programming to determine the maximum number of indices we can visit.

First, we create a sorted list of indices based on their corresponding values in the input array. We then use a DP array where dp[i] indicates the maximum number of indices we can reach starting from index i.

By iterating over this sorted list, we try to update our DP array based on valid jumps that comply with the problem's constraints. This ensures that each index is processed in order of increasing heights, allowing efficient computation of possible jumps.

This solution involves sorting the indices based on height in ascending order and uses a DP array to track the maximum indices reachable from each. Jumps are considered both left and right within distance and height constraints.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log n + n * d), due to sorting and checking possible positions for each index.

Space Complexity: O(n), necessitated by the storage for indices and the DP array.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Dynamic Programming with Depth-First Search (DFS)	Time Complexity: O(n * d), where n is the length of the array, and d is the distance constraint. Each index is visited at most once due to memoization. Space Complexity: O(n), for the DP array used in the solution.
Sorting with Dynamic Programming	Time Complexity: O(n log n + n * d), due to sorting and checking possible positions for each index. Space Complexity: O(n), necessitated by the storage for indices and the DP array.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Dynamic Programming with DFS (Memoization)	O(n*d)	O(n)	General solution. Best for interviews because it models the problem as graph traversal with memoized DP.
Sorting with Dynamic Programming	O(n log n + n*d)	O(n)	When you want to avoid recursion and process states in dependency order using sorted heights.

Video Solution

Watch 9 more video solutions →

Frequently Asked Questions

Is Jump Game V easy or hard?

Jump Game V is classified as Hard because it combines constrained traversal with dynamic programming. The challenge is recognizing overlapping subproblems and preventing redundant exploration using memoization or ordered DP processing.

How to solve Jump Game V in O(n*d)?

Use DFS with memoization. For each index i, attempt jumps up to distance d to the left and right while the destination height is strictly smaller. Stop when encountering an equal or larger value. Store results in a dp array so each index is computed once, leading to O(n*d) total work.

What is the best approach for Jump Game V?

The most common solution uses depth-first search with memoized dynamic programming. From each index, explore valid jumps left and right within distance d while the next value is smaller. Memoization stores the maximum jumps starting from each index, giving an overall time complexity of O(n*d) and space complexity of O(n).

Is Jump Game V asked at Google/Amazon/Meta?

Jump Game style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test dynamic programming, graph traversal, and state transitions. Variants such as Jump Game I, II, IV, and V are commonly used to evaluate problem‑solving depth.

What data structure is used in Jump Game V?

The main structure is a dynamic programming array that stores the maximum reachable indices from each position. The DFS approach also uses recursion to traverse possible jumps, effectively treating the array as a directed graph where edges represent valid moves.

What is the time complexity of Jump Game V?

The optimal DFS with memoization solution runs in O(n*d) time because each index explores at most d positions in both directions once. Space complexity is O(n) for the memoization array and recursion stack. A sorting-based DP approach runs in O(n log n + n*d) due to sorting the indices by height.

Jump Game V Python or Java solution approach?

Both Python and Java implementations typically use DFS with memoization. Define a recursive function dfs(i) that returns the maximum jumps starting from index i, cache results in a dp array, and iterate up to distance d in both directions while maintaining the height constraint.

Ready to solve this problem?

Practice Jump Game V with our built-in code editor and test cases.

Practice on FleetCode

Jump Game VII

Jump Game VIII

Problem Info

DifficultyHard

Acceptance75.7%

Approaches3

Reading time18 min

Asked at

Amazon Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Dynamic Programming with Depth-First Search (DFS)

Code

Complexity

Approach 2: Sorting with Dynamic Programming

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents