We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Jump Game III

Difficulty: Medium

Problem Description

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 cannot jump outside of the array at any time.

Key Insights

  • The problem can be approached using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all possible indices reachable from the starting index.
  • We need to keep track of visited indices to avoid cycles and redundant checks.
  • The goal is to determine if any of the reachable indices have a value of 0.

Space and Time Complexity

Time Complexity: O(n) - In the worst case, we may visit every index once.
Space Complexity: O(n) - We need to store visited indices, which can be up to the size of the array.

Solution

To solve the problem, we can use the BFS algorithm. We start from the given start index and explore both possible jumps (i + arr[i] and i - arr[i]). We maintain a queue to track indices to be explored and a set to track visited indices. If we reach an index with a value of 0 during our exploration, we return true. If we exhaust all possibilities without finding a zero, we return false.

Code Solutions

from collections import deque

def canReach(arr, start):
    queue = deque([start])
    visited = set()
    
    while queue:
        index = queue.popleft()
        
        # Check if we reached a zero index
        if arr[index] == 0:
            return True
        
        # Check the two possible jumps
        for jump in (index + arr[index], index - arr[index]):
            if 0 <= jump < len(arr) and jump not in visited:
                visited.add(jump)
                queue.append(jump)
    
    return False
← Back to All Questions