Problem Statement in English

You’re given a 0-indexed integer array 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)).

Return the maximum number of indices you can visit. You can start at any index and you can jump to the same index multiple times.

Approach

You need to calculate the maximum number of indices you can visit starting from each index. This can be done using a depth-first search (DFS) approach in the left and right directions, with memoization to avoid redundant calculations.

Then you can just put it together and find the maximum number of indices you can visit starting from any index.

The reason there are no cycles in this problem is that you can only jump to indices with smaller values, which means you will never revisit an index once you’ve jumped away from it. The question solves that problem for you :)

And we’re done!

Solution in Python


class Solution:
    def maxJumps(self, arr: list[int], d: int) -> int:
        n = len(arr)
        
        @cache
        def dfs(i: int) -> int:
            max_steps = 1  # You can always at least visit the starting index itself
            
            # 1. Look to the right (i + x)
            for x in range(1, d + 1):
                j = i + x
                if j >= n or arr[j] >= arr[i]:
                    break  # Blocked by boundary or an equal/higher wall
                max_steps = max(max_steps, 1 + dfs(j))
                
            # 2. Look to the left (i - x)
            for x in range(1, d + 1):
                j = i - x
                if j < 0 or arr[j] >= arr[i]:
                    break  # Blocked by boundary or an equal/higher wall
                max_steps = max(max_steps, 1 + dfs(j))
                
            return max_steps

        # Try starting from every possible index and find the absolute maximum
        return max(dfs(i) for i in range(n))

Complexity

  • Time: $O(n \cdot d)$
    Since we are trying to jump from each index and for each index, we can jump up to d steps in both directions. In the worst case, we might explore all possible jumps for each index, leading to a time complexity of $O(n \cdot d)$.

  • Space: $O(n \cdot d)$
    Since we are using memoization to store results for each index, and in the worst case, we might store results for all indices and all possible jumps, leading to a space complexity of $O(n \cdot d)$.

And we are done.