https://leetcode.com/problems/jump-game-iii

This is in fact graph traversal problem: given start position and moving rules, we need to check if we can reach node with value 0. There are as usual 3 classical approaches how you can do it:

  1. bfs, using queue
  2. dfs, using stack
  3. dfs, using recursion

In this problem, dimensions are not very big, so we can actually choose any of the methods. I chose dfs, using stack, so, what we have here:

stack is what we keep for our dfs traversal, visited is already visited indexes, so we will not have infinite loop. As usual, we extract element from the top of our stack, and if arr[pos] equal to zero, we reached our goal and we return True. Then we mark our node as visited and try to make two jumts: forward and backward. We do them only we did not visited these indexes yet.

Complexity: Time complexity is O(n), where n is size of our arr: we only traverse indexes in this array. Space complexity is O(n) as well to keep array of visited nodes (or we can modify arr, but I think it is a bit of a cheat).

class Solution:
    def canReach(self, arr, start):
        stack, visited, n = [start], set(), len(arr)
        
        while stack:
            pos = stack.pop()
            if arr[pos] == 0: return True
            visited.add(pos)
            cand1, cand2 = pos + arr[pos], pos - arr[pos]
            if cand1 <  n and cand1 not in visited: stack.append(cand1)
            if cand2 >= 0 and cand2 not in visited: stack.append(cand2)
                
        return False

If you like the solution, you can upvote it on leetcode discussion section: Problem 1306