Jump Game V - Leetcode Solution

Problem:

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 choose to start at index 6, your maximum number of visited indices is 3.

Example 2:

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

Solution:

The idea is to start from each index, calculate the maximum number of indices that you can visit, and return the maximum value over all the starting indices. To calculate the maximum number of indices that you can visit starting from a given index, we can use dynamic programming.

Create a dp array of size n, where dp[i] represents the maximum number of indices we can visit starting from index i. Initially, initialize dp[i] to 1. This is because we can always stay in place, so we can visit at least one index.

To calculate dp[i], we need to consider all the indices to which we can jump from index i. We can jump to indices i + x and i - x, where x is between 1 and d and the indices i + x and i - x are within the bounds of the array. We can jump to an index j only if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j.

Thus, we can iterate over x from 1 to d, and for each x, we can check if we can jump to any index j such that arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j. If we can jump to index j, then we can update dp[i] as max(dp[i], 1 + dp[j]).

Finally, we can return the maximum value in the dp array as the answer.

Here is the Python code:

def maxJumps(self, arr: List[int], d: int) -> int: n = len(arr) dp = [1]*n

def jump(i):
    res = 0
    for x in range(1, d+1):
        if i+x < n and arr[i+x] < arr[i]:
            res = max(res, dp[i+x])
        else:
            break
    for x in range(1, d+1):
        if i-x >= 0 and arr[i-x] < arr[i]:
            res = max(res, dp[i-x])
        else:
            break
    return res

indices = list(range(n))
indices.sort(key=lambda i: arr[i])

for i in indices:
    dp[i] = 1 + jump(i)

return max(dp)

1