#1306

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Jump Game III

Jump Game III challenges you to determine if you can reach any zero in an array using jumps defined by array values, testing DFS and BFS.

array depth first search breadth first search

Problem Statement

You are given a non-negative integer array arr and a starting index start. From index i, you can jump to i + arr[i] or i - arr[i]. Determine if there exists a sequence of jumps that lands on any index with value 0 without going outside the array bounds.

Return true if it is possible to reach an index with value 0 starting from start; otherwise, return false. You cannot jump outside the array. For example, given arr = [4,2,3,0,3,1,2] and start = 5, one valid path is index 5 -> index 4 -> index 1 -> index 3.

Examples

Example 1

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

Output: true

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

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

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

Solution Approach

Depth-First Search Approach

Perform DFS from the start index, marking visited indices to avoid cycles. Recursively explore both forward and backward jumps based on arr[i]. If any recursive path reaches a zero, return true immediately; otherwise, continue until all options are exhausted.

Breadth-First Search Approach

Use BFS to systematically explore all reachable indices level by level, starting from the start index. Maintain a queue and visited set to prevent reprocessing. If any index with value zero is found during BFS, return true; otherwise, continue until the queue is empty.

Visited Tracking and Optimization

Avoid revisiting indices by marking them or using a visited set. This prevents infinite loops from cycles in the jump paths and ensures time complexity remains manageable. Early termination is critical once a zero is reached.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each index is visited at most once. Space complexity is O(n) due to the visited set and the recursion stack for DFS or the queue for BFS.

What Interviewers Usually Probe

Focus on array traversal patterns using DFS/BFS.
Check for cycles to avoid infinite loops.
Consider edge cases where start index is already zero.

Common Pitfalls or Variants

Common pitfalls

Not marking visited indices leading to infinite loops.
Assuming jumps can go outside the array bounds.
Forgetting to check both forward and backward jumps at each index.

Follow-up variants

Use a weighted jump array where arr[i] is the maximum jump length.
Allow multiple start indices instead of a single start.
Determine the minimum number of jumps to reach zero instead of just reachability.

FAQ

What is the key pattern in Jump Game III?

The main pattern is an array plus depth-first or breadth-first search, tracking jumps both forward and backward.

Can I jump outside the array in Jump Game III?

No, any jump that would leave the array bounds is invalid and must be ignored.

What data structures are recommended to solve Jump Game III efficiently?

Use a visited set or array to track processed indices and either a recursion stack for DFS or a queue for BFS.

How do I handle cycles in Jump Game III?

Mark indices as visited before exploring jumps to prevent revisiting and infinite loops.

Is BFS better than DFS for Jump Game III?

BFS can find the shortest path to a zero, but both BFS and DFS are valid; choice depends on preference and space constraints.

terminal

Solution

Solution 1: BFS

We can use BFS to determine whether we can reach the index with a value of $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        q = deque([start])
        while q:
            i = q.popleft()
            if arr[i] == 0:
                return True
            x = arr[i]
            arr[i] = -1
            for j in (i + x, i - x):
                if 0 <= j < len(arr) and arr[j] >= 0:
                    q.append(j)
        return False

Continue Practicing

#1267 count servers that communicate #1254 number of closed islands #1391 check if there is a valid path in a grid