Problem statement

https://leetcode.com/problems/minimum-jumps-to-reach-home/

Solution

Let us use bfs, where we keep number of steps we made and also state of visited position: 1 if we visit it, using forward step and 2 if we visit it using backward jump. We use classical bfs with some fixed parts. We will keep in our queue tuples with 3 elements: number of steps, position and direction from where we visit this position. Also we keep set of visited positions as tuples, first one is coordinate and second one is direction, from which it was visited.

  1. Try to do forward step if we are less than LIMIT (good exercise is to prove how we choose LIMIT, the idea that after this place we always can make step back and forward and approximately stay on the same place, using gcd): maximum reaching point we need to check, it can be evaluated as maximum number from forbidden plus a plus b. Also check that new position not visited already from left side, that is (curr + a, 0) not in our forb set. Then we put new element into our queue and add new element to forb.

  2. If last direction was to the right, we can also make move to the left now: we again check if this position is visited. If this is forbidden position or it is visited from left already (meaning curr - b, 0 in forb}, then no need to visit it again: either it is forbidden, or we visit it already previously, which means that we make it in less or equal number of steps and we visited it, doing right step, that is more powerful than this position, reached using left step.

    Also, it can not happen, that this position already visited from left, so no need to check condition (curr - b, 1) not in forb.

Complexity

Time complexity is O(a + b + max(x, F)), where F is the biggest number in forbidden, because we have this number of states and we visit each state only twice: from left and right. Space complexity is the same.

Code

class Solution:
    def minimumJumps(self, forbidden, a, b, x):
        forb = set([(f, 0) for f in forbidden])
        forb.add((0, 0))
        queue, LIMIT = deque([(0, 0, 1)]), max(x+a+b, max(forbidden)+a+b)
        
        while queue:
            steps, curr, dr = queue.popleft()
            if curr == x: return steps
            
            if curr + a <= LIMIT and (curr + a, 0) not in forb:
                queue.append((steps + 1, curr + a, 1))
                forb.add((curr + a, 0))
            if dr == 1 and curr - b >= 0 and (curr - b, 0) not in forb:
                queue.append((steps + 1, curr - b, -1))
                forb.add((curr - b, 1))

        return -1