1306. Jump Game III

/**
 * Problem: LeetCode 1306 - Jump Game III
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            // Target reached: current index has value 0
            if (arr[curr] == 0) {
                return true;
            }

            // Jump forward: curr + arr[curr]
            int forward = curr + arr[curr];
            if (forward < n && !visited[forward]) {
                visited[forward] = true;
                queue.offer(forward);
            }

            // Jump backward: curr - arr[curr]
            int backward = curr - arr[curr];
            if (backward >= 0 && !visited[backward]) {
                visited[backward] = true;
                queue.offer(backward);
            }
        }

        return false;
    }
}

"""
Problem: LeetCode 1306 - Jump Game III
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List
from collections import deque

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        queue = deque([start])
        visited = [False] * n
        visited[start] = True

        while queue:
            curr = queue.popleft()

            # Target reached: current index has value 0
            if arr[curr] == 0:
                return True

            # Jump forward: curr + arr[curr]
            forward = curr + arr[curr]
            if forward < n and not visited[forward]:
                visited[forward] = True
                queue.append(forward)

            # Jump backward: curr - arr[curr]
            backward = curr - arr[curr]
            if backward >= 0 and not visited[backward]:
                visited[backward] = True
                queue.append(backward)

        return False

/**
 * Problem: LeetCode 1306 - Jump Game III
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        queue<int> q;
        vector<bool> visited(n, false);

        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            // Target reached: current index has value 0
            if (arr[curr] == 0) {
                return true;
            }

            // Jump forward: curr + arr[curr]
            int forward = curr + arr[curr];
            if (forward < n && !visited[forward]) {
                visited[forward] = true;
                q.push(forward);
            }

            // Jump backward: curr - arr[curr]
            int backward = curr - arr[curr];
            if (backward >= 0 && !visited[backward]) {
                visited[backward] = true;
                q.push(backward);
            }
        }

        return false;
    }
};

/**
 * Problem: LeetCode 1306 - Jump Game III
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var canReach = function(arr, start) {
    const n = arr.length;
    const queue = [start];
    const visited = new Uint8Array(n);
    visited[start] = 1;

    let head = 0;
    while (head < queue.length) {
        const curr = queue[head++];

        // Target reached: current index has value 0
        if (arr[curr] === 0) {
            return true;
        }

        // Jump forward: curr + arr[curr]
        const forward = curr + arr[curr];
        if (forward < n && !visited[forward]) {
            visited[forward] = 1;
            queue.push(forward);
        }

        // Jump backward: curr - arr[curr]
        const backward = curr - arr[curr];
        if (backward >= 0 && !visited[backward]) {
            visited[backward] = 1;
            queue.push(backward);
        }
    }

    return false;
};