HardNo. 1340
Jump Game V — LeetCode 1340 Python Solution
- Pattern
- Sorting
- Topics
- Array, Dynamic Programming, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
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
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
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
| No. | Problem | Difficulty |
|---|---|---|
| 0055 | Jump Game | Medium |
| 0368 | Largest Divisible Subset | Medium |
| 0435 | Non-overlapping Intervals | Medium |
| 0472 | Concatenated Words | Hard |
| 0646 | Maximum Length of Pair Chain | Medium |
| 0975 | Odd Even Jump | Hard |
Frequently asked questions
- How hard is LeetCode 1340. Jump Game V?
LeetCode 1340. Jump Game V is rated Hard on LeetCode.
- What topics does LeetCode 1340. Jump Game V cover?
LeetCode 1340. Jump Game V is tagged Array, Dynamic Programming and Sorting on LeetCode.