Jump Game V LeetCode solution in Java

1
class Solution {
2
  public int maxJumps(int[] arr, int d) {
3
    List jumpsFrom[] = new List[arr.length]; // find all possible jumps from each spot
4
    findJumps(arr, d, true, jumpsFrom); // add left jumps (itareting left to right)
5
    findJumps(arr, d, false, jumpsFrom); // add right jumps
6
    int jumpChain[] = new int[arr.length], max = 1; // 0 - unvisited
7
    for (int i = 0; i < arr.length; i++) {
8
      if (jumpChain[i] == 0) {
9
        jumpChain[i] = dfs(arr, jumpChain, jumpsFrom, i);
10
        max = Math.max(max, jumpChain[i]);
11
      }
12
    }
13
    return max;
14
  }
15

16
  private void findJumps(int[] arr, int d, boolean left, List jumpsFrom[]) {
17
    Stack<Integer> s = new Stack();
18
    int i = (left) ? 0 : arr.length - 1;
19
    while (i >= 0 && i < arr.length) {
20
      if (left) jumpsFrom[i] = new ArrayList();
21
      while (!s.isEmpty()
22
          && arr[i]
23
              > arr[s.peek()]) { // pop stack until higher step found from left/right, adding all
24
        // left/right lower jumps from i
25
        int lowerIndex = s.pop();
26
        if (Math.abs(i - lowerIndex) <= d) jumpsFrom[i].add(lowerIndex);
27
        else s = new Stack(); // past d steps
28
      }
29
      s.push(i);
30
      i += (left) ? 1 : -1;
31
    }
32
  }
33

34
  private int dfs(int[] arr, int jumpChain[], List<Integer> jumpsFrom[], int start) {
35
    int max = 1;
36
    for (int i : jumpsFrom[start]) {
37
      if (jumpChain[i] == 0) jumpChain[i] = dfs(arr, jumpChain, jumpsFrom, i);
38
      max = Math.max(max, 1 + jumpChain[i]);
39
    }
40
    return max;
41
  }
42
}