Jump Game III

class Solution {
public:
    bool isReachable(vector<int>& arr, int position) {
        if (position >= 0 and position < arr.size() and arr[position] >= 0) {
            if (arr[position] == 0) {
                return true;
            }
            int jump = arr[position];
            arr[position] = -jump; // mark as visited by negating
            return isReachable(arr, position + jump) || isReachable(arr, position - jump);
        }
        return false;
    }
};

In the "Jump Game III" task, implemented in C++, you aim to determine if you can reach a position marked with a 0 value in the provided array. Starting at a given position, you can jump either forward or backward by the number indicated at the current position.

The provided code implements a recursive approach to solve this problem:

• It first checks if the current position is within viable array bounds and that the value at the position hasn't been visited yet. The visited check is performed by ensuring the value isn't negative.
• If the current element is 0, the function returns true, indicating that a zero has been reached.
• The current element's value is then negated to mark it as visited, preventing infinite loops caused by revisiting the same array positions.
• The algorithm recursively checks both possible jumps (forward and backward) from the current position. If either recursive call returns true, indicating that a path to 0 was found, the function itself returns true.
• If neither jump leads to a position with 0, or the position is outside of the array bounds, then false is returned, indicating that it's not possible to reach a position with 0 from the starting position using legal jumps.

This recursive approach effectively explores all potential paths from the starting position, leveraging backtracking by negation of array values to mark visited positions, ensuring an efficient exploration without redundant checks.

class Solution {

    public boolean isReachable(int[] data, int initial) {
        if (initial >= 0 && initial < data.length && data[initial] >= 0) {
            if (data[initial] == 0) {
                return true;
            }
            data[initial] = -data[initial];
            return (
                isReachable(data, initial + data[initial]) ||
                isReachable(data, initial - data[initial])
            );
        }
        return false;
    }
}

This solution addresses the problem of determining whether it’s possible to reach an index holding the value 0 in an integer array where each index enables a jump of magnitude equal to its value, either forwards or backwards. The Java function isReachable() implements this logic using recursion and a strategy for marking visited indices to avoid infinite loops.

Implement the solution as follows:

1. Check if the current index initial is within the bounds of the array and the value at this index has not been visited (indicated by a non-negative value).
2. Confirm if the current index holds the value 0. If so, return true as the goal is achieved.
3. Mark the current index as visited by negating its value. This prevents cycles during recursion.
4. Recursively attempt to jump forwards by the value at the current index and backwards by the same amount.
5. If either recursive call returns true, then the index 0 is reachable from the initial position, thus return true.
6. If no valid index is reachable, return false.

This method effectively utilizes recursion to explore potential jump paths and uses negation for marking indices as visited, ensuring that each index is processed only once. This approach avoids unnecessary recomputation and infinite loops, making it efficient for solving the problem within varying sized arrays.

class Solution:
    def isReachable(self, data: List[int], origin: int) -> bool:
        if 0 <= origin < len(data) and data[origin] >= 0:
            if data[origin] == 0:
                return True

            data[origin] = -data[origin]  # Mark the cell as visited
            # Recursively check the next possible jumps from the current index
            return self.isReachable(data, origin + data[origin]) or self.isReachable(
                data, origin - data[origin]
            )

        return False

The provided solution for the "Jump Game III" problem uses a recursive approach to check if the user can reach an array position with a value of zero starting from a given index in the array. Below is a breakdown of how the Python code achieves this:

1. Define a method isReachable that takes two parameters, data, an array of integers, and origin, an integer representing the starting index.
2. Check if the current index is within the bounds of the array and not previously visited (indicated by a non-negative value).
3. If the current value at the index is zero, return True because a zero value means the position is reachable.
4. Mark the current index as visited by negating the value at that index to avoid revisiting it.
5. Recursively call isReachable for the next potential positions, origin + data[origin] (jump right) and origin - data[origin] (jump left), and return True if either recursive call returns True.
6. If none of the above conditions are met, return False indicating that the position with zero value is not reachable from the given starting index.

The use of recursion makes this approach straightforward, relying on the principle of exploring each option (jump right or left) until a solution is found or all possibilities are exhausted. Ensure that there is sufficient recursion depth or an alternative strategy if the array size is large, as deep recursion might cause a stack overflow.