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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Jump Game III

Number: 1428

Difficulty: Medium

Paid? No

Companies: Microsoft, Pinterest, Snap, Goldman Sachs

Problem Description

Given an array of non-negative integers arr and a starting index, determine whether you can reach any index in the array where the value is 0 by making jumps. At index i, you can jump to either i + arr[i] or i - arr[i], as long as the new index remains within array bounds.

Key Insights

  • The problem can be modeled as a graph traversal where each index is a node and jumps represent edges.
  • Use Breadth-First Search (BFS) or Depth-First Search (DFS) to explore reachable indices.
  • A visited array (or set) is necessary to avoid re-visiting indices and falling into cycles.
  • When an index with value 0 is found, the answer is true.
  • Each index is processed at most once ensuring an efficient solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We solve the problem using a BFS approach. Starting at the given index, we enqueue the starting index and mark it as visited. For every index dequeued, if its value is 0, the function returns true. Otherwise, we calculate its forward (i + arr[i]) and backward (i - arr[i]) move. If these moves lead to valid, unvisited indices, we mark them as visited and add them to the queue. If we exhaust all possibilities without finding a 0, the function returns false. Using BFS ensures that each index is visited only once, thereby efficiently solving the problem.

Code Solutions

# Python implementation using BFS
from collections import deque

def canReach(arr, start):
    # Total number of indices in the array
    n = len(arr)
    # Keep track of visited indices to avoid cycles
    visited = [False] * n
    # Initialize the BFS queue with the starting index
    queue = deque([start])
    visited[start] = True
    
    while queue:
        current = queue.popleft()
        # If a cell with value 0 is reached, return True
        if arr[current] == 0:
            return True
        
        # Calculate next indices based on current index's value
        forward = current + arr[current]
        backward = current - arr[current]
        
        # Check the forward jump
        if 0 <= forward < n and not visited[forward]:
            visited[forward] = True
            queue.append(forward)
        
        # Check the backward jump
        if 0 <= backward < n and not visited[backward]:
            visited[backward] = True
            queue.append(backward)
    
    # Return False if no index with value 0 is reachable
    return False

# Example usage:
print(canReach([4,2,3,0,3,1,2], 5))  # Expected output: True
← Back to All Questions