Jump Game V — LeetCode 1340 Python Solution

The 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.

Example

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.

Python solution

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

        n = len(arr)
        return max(dfs(i) for i in range(n))

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1340. Jump Game V is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems