Jump game iii

Array Depth-First Search Breadth-First Search

66.7% acceptance

Feb 25, 2026

4331

117

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_reach(arr: Vec<i32>, start: i32) -> bool {
    let n = arr.len();
    let mut visited = vec![false; n];
    let mut stack = vec![start as usize];
    while let Some(i) = stack.pop() {
      if arr[i] == 0 { return true; }
      if visited[i] { continue; }
      visited[i] = true;
      let v = arr[i] as usize;
      if i + v < n { stack.push(i + v); }
      if i >= v { stack.push(i - v); }
    }
    false
  }
}