Minimum Jumps to Reach Home: BFS with Directional State

LeetCode Minimum Jumps to Reach Home (Problem 1654) asks you to find the minimum number of jumps a bug needs to reach a target position on a number line, given that some positions are forbidden and the bug cannot jump backward twice in a row.

The problem

A bug sits at position 0 on an infinite number line. It wants to reach position x. On each move it can jump forward by exactly a positions or backward by exactly b positions. There are two constraints: certain positions in the forbidden array are permanently off limits, and the bug cannot make two consecutive backward jumps.

Given forbidden, a, b, and x, return the minimum number of jumps to reach x, or -1 if the bug can never get there.

The brute force approach

A naive strategy is to try every possible sequence of forward and backward jumps using recursion. At each position you branch into two choices (jump forward or jump backward), filtering out forbidden positions and the consecutive-backward rule. This produces an exponential number of paths and will time out on any non-trivial input.

The problem screams "shortest path" since you want the minimum number of moves. That points directly to BFS.

The key insight

You might think the BFS state is just the position. But that misses a critical detail: whether you are allowed to jump backward depends on your previous move. If the bug just jumped backward, it cannot jump backward again. If it just jumped forward, it can go either direction.

So the real state is a pair: (position, last_was_backward). Two visits to the same position with different backward flags are distinct states. A BFS node at (6, false) means the bug is at position 6 and its last jump was forward, while (6, true) means it is at 6 but its last jump was backward. The first state allows both forward and backward moves; the second only allows forward.

The second subtlety is the search boundary. The number line is infinite, so you need an upper limit to stop BFS from running forever. A safe bound is 2000 + a + b. The bug never needs to go beyond max(x, max(forbidden)) + a + b because any useful backward jump from a higher position can be reached within that range.

Step-by-step walkthrough

Let's trace through the example forbidden = [14, 4, 18, 1, 15], a = 3, b = 15, x = 9. The bug can jump forward 3 or backward 15.

In this case the bug never needs a backward jump. It hops forward three times: 0 to 3, 3 to 6, 6 to 9. The forbidden positions (1, 4, 14, 15, 18) do not block this path. BFS confirms that 3 is the minimum because no shorter path exists.

The code

from collections import deque

def minimum_jumps(forbidden: list[int], a: int, b: int, x: int) -> int:
    max_pos = max(x, max(forbidden, default=0)) + a + b
    forbidden_set = set(forbidden)
    visited = set()
    visited.add((0, False))
    queue = deque([(0, False, 0)])

    while queue:
        pos, last_back, jumps = queue.popleft()

        if pos == x:
            return jumps

        forward = pos + a
        if forward <= max_pos and forward not in forbidden_set and (forward, False) not in visited:
            visited.add((forward, False))
            queue.append((forward, False, jumps + 1))

        if not last_back:
            backward = pos - b
            if backward >= 0 and backward not in forbidden_set and (backward, True) not in visited:
                visited.add((backward, True))
                queue.append((backward, True, jumps + 1))

    return -1

After building the forbidden set and establishing the upper bound, BFS explores states level by level. Each state tracks position, whether the last jump was backward, and the jump count. Forward jumps always produce a (pos + a, False) state. Backward jumps produce a (pos - b, True) state but are only allowed when last_back is False.

Complexity analysis

Here max_pos is the upper bound on positions, roughly max(x, max(forbidden)) + a + b. Each position has two possible states (last jump forward or backward), so BFS visits at most 2 * max_pos states. Each state does constant work. The visited set and queue together use O(max_pos) space.

In the worst case with the LeetCode constraints (x, a, b, and forbidden values up to 2000), max_pos is at most around 6000, making this very efficient.

The building blocks

1. BFS on an implicit graph with augmented state

The core template for shortest-path BFS applies here, but with the twist of an extra boolean in the state:

queue = deque([(start_pos, False, 0)])
visited = {(start_pos, False)}

while queue:
    pos, last_back, dist = queue.popleft()
    if pos == target:
        return dist
    for next_pos, next_back in get_neighbors(pos, last_back):
        if (next_pos, next_back) not in visited:
            visited.add((next_pos, next_back))
            queue.append((next_pos, next_back, dist + 1))

This pattern recurs in any problem where your movement rules depend on your previous action. The state needs to encode enough history to determine which moves are legal from the current position.

2. Bounding an infinite search space

When the graph has no natural boundary (an infinite number line, unbounded coordinates), you must establish a safe upper limit. The reasoning is: if the bug overshoots x by more than a + b, it can never get back. So positions beyond max(x, max(forbidden)) + a + b are unreachable in any optimal solution.

This bounding technique appears whenever BFS runs on an infinite or very large implicit graph. Proving the bound is the key step; once you have it, BFS proceeds normally within a finite space.

Edge cases

• x is 0: The bug is already at the target. Return 0 immediately.
• x is in forbidden: The target itself is unreachable. Return -1.
• a equals b: The bug can only reach multiples of a (since forward and backward cancel out). If x is not a multiple of a, or if a required stepping stone is forbidden, return -1.
• No backward jump needed: When x is a multiple of a and no forbidden position sits on the path 0, a, 2a, ..., x, the answer is simply x / a.

From understanding to recall

You now see why this problem needs BFS with a (position, last_backward) state pair, a forbidden set for O(1) lookups, and an upper bound to contain the search. Reading through the logic makes it click. But reproducing it under interview pressure is a different challenge. You need the BFS template, the state design, and the bound calculation to flow from memory.

Spaced repetition turns understanding into automatic recall. CodeBricks drills the augmented-state BFS pattern and the search-space bounding technique as separate building blocks. You type each piece from scratch at increasing intervals until it becomes second nature. When an interview problem hands you a number line with constraints, you do not pause to rederive the state space. You just write it.

Related posts

• Open the Lock - BFS shortest path on an implicit state-space graph with blocked nodes
• Jump Game - Greedy reachability on a number line, a simpler variant of position-based movement problems
• Shortest Path in Binary Matrix - BFS shortest path on a grid, showing the same level-by-level expansion pattern