Jump Game III - Video Solutions

Problem Overview: You are given an array arr and a starting index start. From index i, you can jump to i + arr[i] or i - arr[i]. The goal is to determine whether you can reach any index whose value is 0. The array behaves like a graph where each index is a node and jumps create edges.

The core challenge is avoiding infinite loops. Since jumps can revisit the same index repeatedly, the solution must track visited positions while exploring reachable indices.

Approach 1: Depth-First Search (DFS) (Time: O(n), Space: O(n))

Treat the array as a graph and explore it using recursion or an explicit stack. Start at the given index and recursively attempt both possible jumps: i + arr[i] and i - arr[i]. Maintain a visited set (or mark elements in-place) to prevent revisiting indices, which would otherwise create cycles. Each index is processed at most once, so the traversal runs in linear time. DFS works well because you only need to check reachability, not the shortest path. If any recursive path reaches an index with value 0, return true immediately.

This approach highlights the connection between arrays and graph traversal problems. You systematically explore neighbors while enforcing boundary checks (0 ≤ index < n) and skipping already visited nodes.

Approach 2: Breadth-First Search (BFS) (Time: O(n), Space: O(n))

BFS explores indices level by level using a queue. Start by pushing the start index into the queue. At each step, pop an index and check if its value is 0. If not, compute the two reachable indices and push valid, unvisited ones into the queue. Mark them as visited immediately to avoid duplicates.

BFS guarantees each index enters the queue at most once, giving the same O(n) time complexity. The space complexity is also O(n) due to the queue and visited tracking. This approach is often easier to reason about iteratively and mirrors standard graph traversal patterns used in many interview problems.

Both DFS and BFS rely on the same insight: the array forms an implicit graph where edges represent legal jumps. Efficient traversal requires marking visited nodes to avoid cycles.

Recommended for interviews: Either DFS or BFS is acceptable since both achieve optimal O(n) time complexity. DFS is slightly shorter to implement recursively, while BFS demonstrates explicit graph traversal skills. Interviewers mainly look for two things: recognizing the problem as a graph reachability problem and preventing infinite loops with a visited structure. Practicing both approaches strengthens understanding of Depth-First Search, Breadth-First Search, and graph-style traversal on an array.