1306. Jump Game III LeetCode Solution

In this guide, you will get 1306. Jump Game III LeetCode Solution with the best time and space complexity. The solution to Jump Game III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Jump Game III solution in C++
Jump Game III solution in Java
Jump Game III solution in Python
Additional Resources

1306. Jump Game III LeetCode Solution image

Problem Statement of Jump Game III

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach any index with value 0.
Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 104
0 <= arr[i] < arr.length
0 <= start < arr.length

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1306. Jump Game III LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1306. Jump Game III LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

1306. Jump Game III LeetCode Solution in Python

class Solution {
 public:
  bool canReach(vector<int>& arr, int start) {
    return canReach(arr, start, vector<bool>(arr.size()));
  }

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