Jump Game III

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 to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3
Constraints:

• 1 <= arr.length <= 5 * 104
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

This is going to an easy one. Just because LeetCode accepted the recursive solution. Lets start.

So we will start from the given index. Every time we have two options, going forward or backward. That can also lead us going out if bounds so we need to have check for that. Now in question statement if you see, we have a constraint which we can use. That is all the numbers are positive. So we can make numbers negative to mark as visited. Thats all right?
Going forward backward and checking if that is visited or not and is it between the bounds. Lets see the code

def jump(arr, start):
        if 0 <= start < len(arr) and arr[start] >= 0:  #line 1
            arr[start] = -arr[start] #line 2
            return arr[start] == 0 or jump(arr, start+arr[start]) or jump(arr, start-arr[start]) #line 3
        return False

We are checking for bounds and visited in the first line. If true, we set it as visited and check if it is 0 else move towards right and left. If first condition is False, return False as 0 can’t exist outside the bounds or it cant be already visited as we always check in line 3.

Refer to this if any doubt.