Jump Game V

Hard
1508.

Jump Game V

Jump Game V is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

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 <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} d
 * @return {number}
 */
var maxJumps = function(arr, d) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length

Hints for Jump Game V

  1. Hint 1

    Every jump goes to a strictly lower value, so no path can loop. The best path from i depends only on the best paths from the indices it can reach.

  2. Hint 2

    Scan outward from i in each direction for at most d steps and stop at the first value that is not lower than arr[i] — it blocks everything behind it.

  3. Hint 3

    Process indices in increasing order of value (or memoise a DFS). Then dp[i] = 1 + max(dp[j]) over the reachable j, 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

  1. Sort the indices by arr[i] in increasing order and set dp[i] = 1 for all i.
  2. Take indices in that order. From i, walk left over j = i-1, i-2, … while j >= 0, i - j <= d and arr[j] < arr[i], updating dp[i] = max(dp[i], dp[j] + 1). Stop at the first arr[j] >= arr[i].
  3. Walk right the same way.
  4. 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