1306. Jump Game III

Problem Statement

link: https://leetcode.cn/problems/jump-game-iii/description/ https://leetcode.com/problems/jump-game-iii/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 can not jump outside of the array at any time.

Example:

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

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

Solution Approach

The solution utilizes a Breadth-First Search (BFS) approach to explore possible jumps from the given starting index, keeping track of visited indices and checking if any index with value 0 is reachable.

Algorithm

1. Initialization: Create a queue with the starting index, initialize a set for visited indices, and get the array length.
2. BFS Traversal: While the queue is not empty, explore possible jumps from the current index, checking for reachability and updating the visited set.
3. Target Check: If an index with value 0 is encountered during the traversal, return True, indicating reachability.
4. Completion: If the queue is empty and no target is found, return False, signifying that no index with value 0 is reachable.

Implement

    class Solution:
      def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        q = [start]
        visited = {start}
        while q:
            cur = q.pop()
            for p in (cur + arr[cur], cur - arr[cur]):
                if 0 <= p < n:
                    if arr[p] == 0:
                        return True
                    if p not in visited:
                        visited.add(p)
                        q.append(p)
        return False
        

    
    

Twitter  facebook  Email