Domain 2MediumMEDIUM

Jump Game III

Determine if a target value of 0 exists at any index reachable from the start position using iterative DFS with cycle detection via a visited set, ensuring O(N) time and space complexity.

Domain: medium•Updated: 2026-09-14
#Depth-First Search#Hash Set#O(N) Time Complexity#O(N) Space Complexity

Problem Breakdown

We need to determine if a specific target condition (finding an index where arr[i] == 0) is reachable from a given starting position. The array defines the graph structure, where each index represents a node and its value determines valid outgoing edges (i + arr[i] or i - arr[i]).

Inputs:

  • arr: List of non-negative integers representing jump lengths at each index.
  • start: Integer indicating the initial current position (index).

Outputs:

  • Boolean: Returns True if any reachable index contains 0, otherwise returns False.

Implicit Constraints & Edge Cases:

  1. Cycles: Since jumps can be reversible or form loops (e.g., A -> B and B -> A), we must track visited indices to prevent infinite processing.
  2. Bounds: Jumps cannot take us outside the array indices [0, len(arr) - 1].
  3. Immediate Target: If arr[start] == 0, return True immediately without further traversal logic (handled naturally by checking current node).
  4. No Path: It is possible that all reachable components do not contain a zero value.

Intuition

This problem can be modeled as finding if there exists a path from the start node to any node with weight 0 in an unweighted directed graph. A brute-force recursive approach would risk hitting recursion depth limits or Time Limit Exceeded (TLE) due to exponential paths without state tracking (O(2N)O(2^N)).

The key insight is recognizing this as a graph reachability problem. We need to explore all reachable components from start. Since edge weights don’t matter for existence, Breadth-First Search (BFS) or Depth-First Search (DFS) are optimal choices. To ensure efficiency and avoid TLE:

  1. Use a visited set to mark indices we have already processed. This prevents cycles and redundant work, ensuring each node is touched at most once (O(N)O(N)).
  2. Implement an iterative approach using a stack or queue instead of deep recursion to handle Python’s default recursion limit safely on large inputs (up to 5×1045 \times 10^4).

Approach

  1. Initialize a set visited and add the start index. Add start to our traversal structure (stack).
  2. While the stack is not empty:
    • Pop an index curr_idx.
    • Check if arr[curr_idx] == 0. If yes, return True.
    • Calculate potential next indices based on jump rules: next = curr + arr[curr] and prev = curr - arr[curr].
  3. For each calculated neighbor:
    • Verify it is within array bounds (>= 0 and < len(arr)).
    • If valid AND not in visited: add to stack, mark as visited immediately (to prevent re-adding).
  4. If the loop completes without finding a zero, return False.

Complexity Analysis

  • Time: O(N)O(N) where NN is the length of arr. Each index enters and leaves the traversal structure at most once due to the visited set check before pushing neighbors. Operations per node are constant time (O(1)O(1)).
  • Space: O(N)O(N). In the worst case, we store all indices in our stack/queue and visited set (e.g., a linear chain of jumps or disconnected components filling memory).

Solution

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        
        # Use iterative DFS to avoid recursion depth issues on large inputs.
        stack = [start]
        visited = {start}

        while stack:
            curr_idx = stack.pop()
            
            # Check if current position is the target value 0
            if arr[curr_idx] == 0:
                return True
            
            # Calculate possible jumps from current index
            next_indices = [curr_idx + arr[curr_idx], curr_idx - arr[curr_idx]]
            
            for nxt in next_indices:
                # Check bounds and visited status before processing
                if 0 <= nxt < n and nxt not in visited:
                    stack.append(nxt)
                    visited.add(nxt)

        return False

Edge Cases Handled

  • Start at Zero: The check if arr[curr_idx] == 0 handles the case where we start on a zero immediately or reach it later.
  • Cycles/Loops: The visited set ensures that if we jump back to an index already processed, it is skipped, preventing infinite recursion or loops.
  • Out of Bounds Jumps: Explicit bounds checking (0 <= nxt < n) prevents accessing invalid memory indices before the loop continues.
  • No Zero Reachable: If the stack empties and no zero was found during traversal, the function correctly returns False.