Skip to content

1306. Jump Game III 👍

Approach 1: BFS

  • 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
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 the 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
class Solution {
  public boolean canReach(int[] arr, int start) {
    final int n = arr.length;
    Queue<Integer> q = new ArrayDeque<>(List.of(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 the 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;
  }
}

Approach 2: DFS

  • 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
class Solution {
 public:
  bool canReach(vector<int>& arr, int start) {
    return canReach(arr, start, vector<bool>(arr.size()));
  }

 private:
  bool canReach(const vector<int>& A, int node, vector<bool>&& seen) {
    if (node < 0 || node >= A.size())
      return false;
    if (seen[node])
      return false;
    if (A[node] == 0)
      return true;
    seen[node] = true;
    return canReach(A, node + A[node], std::move(seen)) ||
           canReach(A, node - A[node], std::move(seen));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean canReach(int[] arr, int start) {
    return canReach(arr, start, new boolean[arr.length]);
  }

  private boolean canReach(int[] A, int node, boolean[] seen) {
    if (node < 0 || node >= A.length)
      return false;
    if (seen[node])
      return false;
    if (A[node] == 0)
      return true;
    seen[node] = true;
    return canReach(A, node + A[node], seen) || canReach(A, node - A[node], seen);
  }
}