Jump Game 3

Problem

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.

Examples

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 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

Solution

Method 1 – BFS (Breadth-First Search)

Intuition

The problem can be visualized as a graph traversal where each index is a node, and you can jump to two possible nodes from each index. BFS is suitable because it explores all possible jumps level by level and avoids revisiting indices, ensuring we find a path to any zero efficiently.

Approach

Initialize a queue with the starting index and a visited array to avoid cycles.
While the queue is not empty:

Pop the current index.
If arr[curr] == 0, return true.
For both possible jumps (curr + arr[curr] and curr - arr[curr]):
- If the new index is within bounds and not visited, add it to the queue and mark as visited.

If the queue is exhausted without finding a zero, return false.

Code

C++

class Solution {
public:
   bool canReach(vector<int>& arr, int start) {
      int n = arr.size();
      queue<int> q;
      vector<bool> vis(n, false);
      q.push(start);
      vis[start] = true;
      while (!q.empty()) {
        int i = q.front(); q.pop();
        if (arr[i] == 0) return true;
        for (int d : {arr[i], -arr[i]}) {
           int ni = i + d;
           if (ni >= 0 && ni < n && !vis[ni]) {
              q.push(ni);
              vis[ni] = true;
           }
        }
      }
      return false;
   }
};

Go

func canReach(arr []int, start int) bool {
   n := len(arr)
   vis := make([]bool, n)
   q := []int{start}
   vis[start] = true
   for len(q) > 0 {
      i := q[0]
      q = q[1:]
      if arr[i] == 0 {
        return true
      }
      for _, d := range []int{arr[i], -arr[i]} {
        ni := i + d
        if ni >= 0 && ni < n && !vis[ni] {
           q = append(q, ni)
           vis[ni] = true
        }
      }
   }
   return false
}

Java

class Solution {
   public boolean canReach(int[] arr, int start) {
      int n = arr.length;
      Queue<Integer> q = new LinkedList<>();
      boolean[] vis = new boolean[n];
      q.offer(start);
      vis[start] = true;
      while (!q.isEmpty()) {
        int i = q.poll();
        if (arr[i] == 0) return true;
        for (int d : new int[]{arr[i], -arr[i]}) {
           int ni = i + d;
           if (ni >= 0 && ni < n && !vis[ni]) {
              q.offer(ni);
              vis[ni] = true;
           }
        }
      }
      return false;
   }
}

Kotlin

class Solution {
   fun canReach(arr: IntArray, start: Int): Boolean {
      val n = arr.size
      val vis = BooleanArray(n)
      val q: ArrayDeque<Int> = ArrayDeque()
      q.add(start)
      vis[start] = true
      while (q.isNotEmpty()) {
        val i = q.removeFirst()
        if (arr[i] == 0) return true
        for (d in listOf(arr[i], -arr[i])) {
           val ni = i + d
           if (ni in 0 until n && !vis[ni]) {
              q.add(ni)
              vis[ni] = true
           }
        }
      }
      return false
   }
}

Python

class Solution:
   def canReach(self, arr: list[int], start: int) -> bool:
      n = len(arr)
      vis = [False] * n
      q = [start]
      vis[start] = True
      while q:
        i = q.pop(0)
        if arr[i] == 0:
           return True
        for d in (arr[i], -arr[i]):
           ni = i + d
           if 0 <= ni < n and not vis[ni]:
              q.append(ni)
              vis[ni] = True
      return False

Rust

impl Solution {
   pub fn can_reach(arr: Vec<i32>, start: i32) -> bool {
      let n = arr.len();
      let mut vis = vec![false; n];
      let mut q = std::collections::VecDeque::new();
      q.push_back(start as usize);
      vis[start as usize] = true;
      while let Some(i) = q.pop_front() {
        if arr[i] == 0 { return true; }
        for &d in &[arr[i], -arr[i]] {
           let ni = i as i32 + d;
           if ni >= 0 && (ni as usize) < n && !vis[ni as usize] {
              q.push_back(ni as usize);
              vis[ni as usize] = true;
           }
        }
      }
      false
   }
}

Complexity

⏰ Time complexity: O(n) — Each index is visited at most once.
🧺 Space complexity: O(n) — For the visited array and queue.