LeetCode 1306 - Jump Game III

The problem gives us an array of non-negative integers and a starting index. From any position i, we are allowed to jump

leetcodemediumarraydepth-first-searchbreadth-first-search

LeetCode Problem 1306

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search

Solution

LeetCode 1306 - Jump Game III

Problem Understanding

The problem gives us an array of non-negative integers and a starting index. From any position i, we are allowed to jump either forward to i + arr[i] or backward to i - arr[i]. The goal is to determine whether it is possible to eventually land on any index whose value is 0.

The important detail is that jumps are determined entirely by the value at the current index. If we are at index i, we do not choose an arbitrary distance. Instead, we must move exactly arr[i] steps either left or right.

The array itself can be viewed as a graph. Each index represents a node, and from each node there are at most two outgoing edges:

  • One edge to i + arr[i]
  • One edge to i - arr[i]

The question becomes whether there exists a path from the starting node to any node containing the value 0.

The constraints are important:

  • The array length can be as large as 5 * 10^4
  • Each value is guaranteed to be within array bounds
  • The starting index is valid

Because the input size is large, we need an algorithm that runs in linear time. Exponential exploration would be far too slow.

One of the biggest dangers in this problem is cycles. Consider an array where indices repeatedly jump back and forth between each other. A naive recursive implementation without tracking visited indices could enter infinite recursion or repeatedly process the same states.

Another important edge case is when the starting index already contains 0. In that situation, the answer should immediately be true.

The problem also guarantees that all numbers are non-negative, which simplifies the movement logic because jump distances are never negative.

Approaches

Brute Force Approach

The brute force idea is to recursively try every possible jump from the current index. At each position, we branch into two possibilities:

  • Jump left
  • Jump right

If either path eventually reaches a 0, we return true.

This approach is conceptually simple because it directly explores every reachable path. However, without remembering previously visited indices, the algorithm can revisit the same positions infinitely many times.

For example, suppose index 2 jumps to 5, and index 5 jumps back to 2. A naive DFS would loop forever.

Even if we artificially stop recursion depth, the number of repeated computations becomes enormous. The same states get explored repeatedly, causing exponential behavior.

Optimal Approach

The key observation is that each index only needs to be processed once.

This is fundamentally a graph traversal problem. Every array index acts like a graph node, and valid jumps form graph edges. We only care whether a path exists to a node containing 0.

A standard graph traversal algorithm such as DFS or BFS works perfectly here. The crucial optimization is maintaining a visited set so we never process the same index more than once.

Once an index has been explored, exploring it again cannot produce new information. This converts the problem from exponential exploration into linear exploration.

We can use either:

  • Depth-First Search using recursion or a stack
  • Breadth-First Search using a queue

Both achieve the same asymptotic complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explores repeated states and may recurse infinitely without protection
Optimal DFS/BFS O(n) O(n) Visits each index at most once

Algorithm Walkthrough

Optimal DFS Algorithm

  1. Create a visited set to track indices we have already explored.
  2. Start a DFS traversal from the given start index.
  3. At each index, first check whether it is out of bounds. If it is, return false because jumps outside the array are invalid.
  4. Check whether the index has already been visited. If so, return false because revisiting the same index would only repeat previous work.
  5. Mark the current index as visited.
  6. Check whether arr[index] == 0. If true, we successfully reached a valid destination, so return true.
  7. Compute the two possible next indices:
  • index + arr[index]
  • index - arr[index]
  1. Recursively explore both possibilities.
  2. If either recursive call returns true, propagate true upward.
  3. If neither path reaches a zero, return false.

Why it works

The algorithm works because it systematically explores every reachable index exactly once. The visited set guarantees that cycles cannot cause infinite recursion or repeated work. Since every legal jump is explored, if a path to a zero exists, the traversal will eventually find it. Conversely, if the traversal finishes without finding a zero, then no reachable path exists.

Python Solution

from typing import List

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = set()

        def dfs(index: int) -> bool:
            if index < 0 or index >= len(arr):
                return False

            if index in visited:
                return False

            visited.add(index)

            if arr[index] == 0:
                return True

            jump = arr[index]

            return dfs(index + jump) or dfs(index - jump)

        return dfs(start)

The implementation begins by creating a visited set. This prevents cycles and ensures every index is processed at most once.

The nested dfs function performs the graph traversal. The first two checks handle invalid states:

  • Out of bounds indices
  • Previously visited indices

After confirming the current index is valid and unvisited, we mark it as explored.

Next, the implementation checks whether the current value equals zero. If so, we immediately return True.

Otherwise, we calculate the jump distance and recursively explore both possible destinations. The logical or operator is important because we only need one successful path.

Finally, the result of the DFS starting from start is returned.

Go Solution

func canReach(arr []int, start int) bool {
    visited := make([]bool, len(arr))

    var dfs func(int) bool

    dfs = func(index int) bool {
        if index < 0 || index >= len(arr) {
            return false
        }

        if visited[index] {
            return false
        }

        visited[index] = true

        if arr[index] == 0 {
            return true
        }

        jump := arr[index]

        return dfs(index+jump) || dfs(index-jump)
    }

    return dfs(start)
}

The Go implementation follows the same logic as the Python version. Instead of using a hash set, it uses a boolean slice named visited, which is more efficient in Go because indices are contiguous integers.

Go also requires explicit declaration of the recursive function variable before assigning the function body. Aside from syntax differences, the traversal logic is identical.

Worked Examples

Example 1

arr = [4,2,3,0,3,1,2]
start = 5

We begin at index 5.

Step Current Index Value Next Indices Visited
1 5 1 6, 4 {5}
2 6 2 8, 4 {5,6}
3 8 Out of bounds Invalid {5,6}
4 4 3 7, 1 {5,6,4}
5 7 Out of bounds Invalid {5,6,4}
6 1 2 3, -1 {5,6,4,1}
7 3 0 Found target {5,6,4,1,3}

The algorithm reaches index 3, whose value is 0, so the answer is true.

Example 2

arr = [4,2,3,0,3,1,2]
start = 0
Step Current Index Value Next Indices Visited
1 0 4 4, -4 {0}
2 4 3 7, 1 {0,4}
3 1 2 3, -1 {0,4,1}
4 3 0 Found target {0,4,1,3}

A valid path exists, so the result is true.

Example 3

arr = [3,0,2,1,2]
start = 2
Step Current Index Value Next Indices Visited
1 2 2 4, 0 {2}
2 4 2 6, 2 {2,4}
3 6 Out of bounds Invalid {2,4}
4 2 Already visited Skip {2,4}
5 0 3 3, -3 {2,4,0}
6 3 1 4, 2 {2,4,0,3}

Eventually all reachable states are exhausted without reaching index 1, which contains 0. Therefore the answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most once
Space O(n) The visited structure and recursion stack may both grow to size n

The algorithm is linear because once an index has been visited, it is never processed again. Every edge exploration therefore occurs at most once per node. The recursion stack can become as deep as the number of reachable indices, which gives the linear space complexity.

Test Cases

from typing import List

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = set()

        def dfs(index: int) -> bool:
            if index < 0 or index >= len(arr):
                return False

            if index in visited:
                return False

            visited.add(index)

            if arr[index] == 0:
                return True

            jump = arr[index]

            return dfs(index + jump) or dfs(index - jump)

        return dfs(start)

solution = Solution()

assert solution.canReach([4,2,3,0,3,1,2], 5) == True  # Provided example 1
assert solution.canReach([4,2,3,0,3,1,2], 0) == True  # Provided example 2
assert solution.canReach([3,0,2,1,2], 2) == False  # Provided example 3

assert solution.canReach([0], 0) == True  # Single element already zero
assert solution.canReach([1,0], 0) == True  # Simple forward jump
assert solution.canReach([1,2,3], 0) == False  # No zero exists
assert solution.canReach([2,4,2,0,1], 2) == False  # Cyclic structure
assert solution.canReach([1,1,1,1,0], 0) == True  # Long forward chain
assert solution.canReach([2,0,1], 2) == True  # Backward jump reaches zero
assert solution.canReach([1,1,1,1,1,1,0], 3) == True  # Reachable from middle
Test Why
[4,2,3,0,3,1,2], start=5 Validates standard reachable path
[4,2,3,0,3,1,2], start=0 Confirms alternate traversal path
[3,0,2,1,2], start=2 Confirms unreachable target handling
[0], start=0 Tests immediate success case
[1,0], start=0 Tests simple one-step jump
[1,2,3], start=0 Tests array without any zero
[2,4,2,0,1], start=2 Tests cycle prevention
[1,1,1,1,0], start=0 Tests long sequential traversal
[2,0,1], start=2 Tests backward movement
[1,1,1,1,1,1,0], start=3 Tests traversal starting in middle

Edge Cases

One important edge case occurs when the starting index already contains 0. A careless implementation might continue exploring neighbors unnecessarily or even fail because no jumps are possible. This implementation handles the case immediately with the check if arr[index] == 0.

Another critical edge case involves cycles. For example, two indices may repeatedly jump back and forth between each other. Without a visited structure, recursive DFS would enter infinite recursion. The visited set guarantees that each index is explored only once.

A third edge case occurs when jumps lead outside the array boundaries. Since negative indices and indices beyond the array length are invalid, the implementation explicitly checks bounds before processing an index. This prevents runtime errors and ensures invalid paths terminate safely.