leetcode

commit 086da5e2ca2957968b3e7963e8509df66e761457
parent 94fcdb79c54feb89603ce90c85cdb53f635aa446
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 24 May 2026 08:36:02 +0300

1340. jump game v

Diffstat:
A
jump_game5.c
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
jump_game5.py
 | 
42
++++++++++++++++++++++++++++++++++++++++++

2 files changed, 96 insertions(+), 0 deletions(-)
diff --git a/jump_game5.c b/jump_game5.c
@@ -0,0 +1,54 @@
+// 1340. Jump Game V
+#include "leetcode.h"
+
+/*
+ * 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',
+ * or 'i - x' where 'i - x >= 0' and '0 < x <= d'. in addition, you 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'. you can choose any index of the array
+ * and start jumping. return the maximum number of indices you can visit.
+ */
+
+void dfs(int *arr, int id, int d, int n, int *f) {
+  if (f[id] != -1)
+    return;
+  f[id] = 1;
+  for (int i = id - 1; i >= 0 && id - i <= d && arr[id] > arr[i]; --i) {
+    dfs(arr, i, d, n, f);
+    if (f[i] + 1 > f[id])
+      f[id] = f[i] + 1;
+  }
+  for (int i = id + 1; i < n && i - id <= d && arr[id] > arr[i]; ++i) {
+    dfs(arr, i, d, n, f);
+    if (f[i] + 1 > f[id])
+      f[id] = f[i] + 1;
+  }
+}
+
+int maxJumps(int *arr, int arrSize, int d) {
+  int n = arrSize, *f = (int *)malloc(n * sizeof(int));
+  memset(f, -1, n * sizeof(int));
+  for (int i = 0; i < n; ++i)
+    dfs(arr, i, d, n, f);
+  int ans = 0;
+  for (int i = 0; i < n; ++i)
+    ans = fmax(ans, f[i]);
+  free(f);
+  return ans;
+}
+
+int main() {
+  int a1[] = {6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12};
+  int a2[] = {3, 3, 3, 3, 3};
+  int a3[] = {7, 6, 5, 4, 3, 2, 1};
+  int r1 = maxJumps(a1, ARRAY_SIZE(a1), 2);
+  int r2 = maxJumps(a2, ARRAY_SIZE(a2), 3);
+  int r3 = maxJumps(a3, ARRAY_SIZE(a3), 1);
+  printf("%d\n", r1);
+  assert(r1 == 4);
+  printf("%d\n", r2);
+  assert(r2 == 1);
+  printf("%d\n", r3);
+  assert(r3 == 7);
+}
diff --git a/jump_game5.py b/jump_game5.py
@@ -0,0 +1,42 @@
+# 1340. 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',
+or 'i - x' where 'i - x >= 0' and '0 < x <= d'. in addition, you 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'. you can choose any index of the array
+and start jumping. return the maximum number of indices you can visit.
+"""
+
+from collections import defaultdict
+
+
+class Solution:
+    def maxJumps(self, arr: List[int], d: int) -> int:
+        n = len(arr)
+        g = defaultdict(list)
+
+        def jump(iter):
+            s = []
+            for i in iter:
+                while s and arr[s[-1]] < arr[i]:
+                    j = s.pop()
+                    if abs(i - j) <= d:
+                        g[j].append(i)
+                s.append(i)
+
+        jump(range(n))
+        jump(reversed(range(n)))
+
+        def height(i):
+            return 1 + max(map(height, g[i]), default=0)
+
+        return max(map(height, range(n)))
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxJumps(arr=[6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12], d=2))
+    print(obj.maxJumps(arr=[3, 3, 3, 3, 3], d=3))
+    print(obj.maxJumps(arr=[7, 6, 5, 4, 3, 2, 1], d=1))