{x}
blog image

Jump Game V

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] <= 105
  • 1 <= d <= arr.length

1340. Jump Game V

Problem Description

Given an array arr of integers and an integer d. You can jump from index i to index i + x or i - x where 0 < x <= d. You can only jump from i to j if arr[i] > arr[j] and arr[i] > arr[k] for all k between i and j. Find the maximum number of indices you can visit.

Solution Explanation

The problem can be solved using dynamic programming or a greedy approach with sorting. Both solutions are presented below.

Solution 1: Dynamic Programming with Memoization

This approach uses recursion with memoization to avoid redundant calculations.

  1. dfs(i) function: This recursive function calculates the maximum number of indices reachable starting from index i.
  2. Base Case: If f[i] (memoization array) already contains a value, it returns the value. Otherwise, it initializes the answer ans to 1 (at least the starting index).
  3. Iteration: It iterates in both directions (j from i-1 to 0 and i+1 to n-1). It checks the jump conditions: |i - j| <= d, arr[i] > arr[j], and that arr[i] is greater than all intermediate elements.
  4. Recursive Call: If the conditions are met, it recursively calls dfs(j) to find the maximum reachable indices from j and updates ans accordingly.
  5. Memoization: After calculation, it updates f[i] with the calculated ans.
  6. Main Loop: The main loop iterates through all indices of the array, calling dfs(i) for each starting index and finding the maximum.

Time Complexity: O(N*d), where N is the length of the array and d is the maximum jump distance. In the worst case, each index might have to explore up to 2d indices. Memoization significantly improves this, making it closer to O(N) in practice. Space Complexity: O(N) for the memoization array f.

Solution 2: Dynamic Programming with Sorting

This approach sorts the array based on the values and uses dynamic programming.

  1. Sorting: Sort the indices of the array based on their values in ascending order.
  2. DP Array: Initialize a DP array f where f[i] stores the maximum number of indices reachable starting from index i.
  3. Iteration: Iterate through the sorted indices. For each index i, explore possible jumps to the left and right, checking the jump conditions as in the previous approach. Update f[i] using the maximum value.
  4. Result: The maximum value in the f array represents the overall maximum number of reachable indices.

Time Complexity: O(N log N) dominated by the sorting step. The dynamic programming part takes O(N*d) in the worst case, but in practice, it is often less. Space Complexity: O(N) for the DP array f.

Code Implementation (Python)

Solution 1 (Memoization)

from functools import cache
 
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        
        @cache
        def dfs(i):
            ans = 1
            for j in range(i - 1, -1, -1):
                if i - j > d or arr[j] >= arr[i]:
                    break
                valid = True
                for k in range(j + 1, i):
                    if arr[k] >= arr[i]:
                        valid = False
                        break
                if valid:
                    ans = max(ans, 1 + dfs(j))
 
            for j in range(i + 1, n):
                if j - i > d or arr[j] >= arr[i]:
                    break
                valid = True
                for k in range(i + 1, j):
                    if arr[k] >= arr[i]:
                        valid = False
                        break
                if valid:
                    ans = max(ans, 1 + dfs(j))
            return ans
 
        return max(dfs(i) for i in range(n))

Solution 2 (Sorting)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        f = [1] * n
        indices = sorted(range(n), key=lambda i: arr[i])
        
        for i in indices:
            for j in range(i - 1, max(-1, i - d -1), -1):
                if arr[j] < arr[i]:
                    valid = True
                    for k in range(j + 1, i):
                        if arr[k] >= arr[i]:
                            valid = False
                            break
                    if valid:
                        f[i] = max(f[i], 1 + f[j])
            for j in range(i + 1, min(n, i + d + 1)):
                if arr[j] < arr[i]:
                    valid = True
                    for k in range(i + 1, j):
                        if arr[k] >= arr[i]:
                            valid = False
                            break
                    if valid:
                        f[i] = max(f[i], 1 + f[j])
 
        return max(f)

Both solutions provide correct results, but the sorting-based approach might be slightly faster in some cases due to avoiding recursion overhead. The choice depends on your preference and the specific constraints of the input data.