Skip to content

1306. Jump Game III 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  bool canReach(vector<int>& arr, int start) {
    const int n = arr.size();
    queue<int> q{{start}};
    vector<bool> seen(n);

    while (!q.empty()) {
      const int node = q.front();
      q.pop();

      if (arr[node] == 0)
        return true;
      if (seen[node])
        continue;

      // Check available next steps
      if (node - arr[node] >= 0)
        q.push(node - arr[node]);
      if (node + arr[node] < n)
        q.push(node + arr[node]);

      seen[node] = true;
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public boolean canReach(int[] arr, int start) {
    final int n = arr.length;
    Queue<Integer> q = new ArrayDeque<>(Arrays.asList(start));
    boolean[] seen = new boolean[n];

    while (!q.isEmpty()) {
      final int node = q.poll();

      if (arr[node] == 0)
        return true;
      if (seen[node])
        continue;

      // Check available next steps
      if (node - arr[node] >= 0)
        q.offer(node - arr[node]);
      if (node + arr[node] < n)
        q.offer(node + arr[node]);

      seen[node] = true;
    }

    return false;
  }
}