Jump Game V — Solution in Python, Java & C++
Jump Game V solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Jump Game V is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array arr and an integer d. From index i you may jump to index j when 1 <= |i - j| <= d and j is inside the array, but only downhill over lower ground: arr[i] > arr[j], and arr[i] > arr[k] for every index k strictly between i and j.
You may start at any index and make as many jumps as you like. Return the maximum number of indices you can visit, counting the starting index.
Example 1
Input: arr = [5,1,4,2,3], d = 2
Output: 4
Explanation: Start at the 5, jump to the 4, then to the 3, then to the 2. From the 2 the 1 is out of reach — the 4 stands between them.
Example 2
Input: arr = [4,4,4,4], d = 2
Output: 1
Explanation: A jump needs strictly lower ground, so no jump is possible.
Example 3
Input: arr = [1,2,3,4,5,6], d = 1
Output: 6
Explanation: Start at the 6 and step down one index at a time.
Constraints
1 <= arr.length <= 10001 <= arr[i] <= 10^51 <= d <= arr.length
Hints for Jump Game V
Hint 1
Every jump goes to a strictly lower value, so no path can loop. The best path from
idepends only on the best paths from the indices it can reach.Hint 2
Scan outward from
iin each direction for at mostdsteps and stop at the first value that is not lower thanarr[i]— it blocks everything behind it.Hint 3
Process indices in increasing order of value (or memoise a DFS). Then
dp[i] = 1 + max(dp[j])over the reachablej, all of which are already final.
How to solve Jump Game V
The jump graph is acyclic because values strictly decrease along every jump. So the longest path from each index is a DP over that DAG, and sorting indices by value gives a valid evaluation order.
Approach
- Sort the indices by
arr[i]in increasing order and setdp[i] = 1for alli. - Take indices in that order. From
i, walk left overj = i-1, i-2, …whilej >= 0,i - j <= dandarr[j] < arr[i], updatingdp[i] = max(dp[i], dp[j] + 1). Stop at the firstarr[j] >= arr[i]. - Walk right the same way.
- Return the largest
dp[i].
Why it works
A jump from i to j requires arr[j] < arr[i], so when i is processed every index it can reach has a smaller value and its dp is already final. The outward walks visit exactly the reachable indices: a value at least arr[i] blocks every index beyond it, and every index before such a blocker is lower than arr[i] together with everything between it and i.
Complexity
- Time —
O(n log n + n · d) - Space —
O(n)
Pitfalls
- Stop the scan at the first blocker in each direction; skipping over it is not allowed.
- Equal values block too — the condition is strictly greater.
- With a recursive DFS, deep chains (a strictly decreasing array) can reach depth n; the sorted bottom-up order avoids recursion entirely.
Reference solution
Python
from typing import List
def maxJumps(arr: List[int], d: int) -> int:
n = len(arr)
order = sorted(range(n), key=lambda i: arr[i])
dp = [1] * n
for i in order:
for step in (-1, 1):
j = i + step
while 0 <= j < n and abs(j - i) <= d and arr[j] < arr[i]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
j += step
return max(dp)Java
public static int maxJumps(int[] arr, int d) {
int n = arr.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(arr[a], arr[b]));
int[] dp = new int[n];
int best = 1;
for (int t = 0; t < n; t++) {
int i = order[t];
dp[i] = 1;
for (int j = i - 1; j >= 0 && i - j <= d && arr[j] < arr[i]; j--) dp[i] = Math.max(dp[i], dp[j] + 1);
for (int j = i + 1; j < n && j - i <= d && arr[j] < arr[i]; j++) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}C++
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return arr[a] < arr[b]; });
vector<int> dp(n, 1);
int best = 1;
for (int i : order) {
for (int j = i - 1; j >= 0 && i - j <= d && arr[j] < arr[i]; j--) dp[i] = max(dp[i], dp[j] + 1);
for (int j = i + 1; j < n && j - i <= d && arr[j] < arr[i]; j++) dp[i] = max(dp[i], dp[j] + 1);
best = max(best, dp[i]);
}
return best;
}JavaScript
var maxJumps = function(arr, d) {
var n = arr.length;
var order = [];
for (var i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return arr[a] - arr[b]; });
var dp = new Array(n).fill(1);
var best = 1;
for (var t = 0; t < n; t++) {
var i = order[t];
for (var j = i - 1; j >= 0 && i - j <= d && arr[j] < arr[i]; j--) dp[i] = Math.max(dp[i], dp[j] + 1);
for (var j = i + 1; j < n && j - i <= d && arr[j] < arr[i]; j++) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming