# Minimum Jumps to Reach Home
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-jumps-to-reach-home)
Canonical: https://scaleengineer.com/dsa/problems/minimum-jumps-to-reach-home
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array
---
## Problem
A certain bug's home is on the x-axis at position `x`. Help them get there from position `0`.

The bug jumps according to the following rules:

* It can jump exactly `a` positions **forward** (to the right).
* It can jump exactly `b` positions **backward** (to the left).
* It cannot jump backward twice in a row.
* It cannot jump to any `forbidden` positions.

The bug may jump forward **beyond** its home, but it **cannot jump** to positions numbered with **negative** integers.

Given an array of integers `forbidden`, where `forbidden[i]` means that the bug cannot jump to the position `forbidden[i]`, and integers `a`, `b`, and `x`, return _the minimum number of jumps needed for the bug to reach its home_. If there is no possible sequence of jumps that lands the bug on position `x`, return `-1.`

**Example 1:**

**Input:** forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
**Output:** 3
**Explanation:** 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

**Example 2:**

**Input:** forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
**Output:** -1

**Example 3:**

**Input:** forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
**Output:** 2
**Explanation:** One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

**Constraints:**

* `1 <= forbidden.length <= 1000`
* `1 <= a, b, forbidden[i] <= 2000`
* `0 <= x <= 2000`
* All the elements in `forbidden` are distinct.
* Position `x` is not forbidden.

# Approaches
## Brute-force Depth First Search (DFS)
This approach uses a classic brute-force recursive method to explore all possible sequences of jumps. It starts from position 0 and, at each step, recursively explores the two possibilities: a forward jump and (if allowed) a backward jump. This method is simple to conceptualize but is highly inefficient as it explores many redundant paths and doesn't inherently find the shortest path without exploring the entire search space.
**Time:** O(2^L), where L is the length of the path. The complexity is exponential as it potentially explores all possible paths up to a certain length, leading to a Time Limit Exceeded error on most platforms. · **Space:** O(L), where L is the maximum depth of the recursion. This space is used for the recursion stack and the `pathVisited` set.
**Pros:** Conceptually simple and easy to implement for a basic understanding of the problem.
**Cons:** Extremely inefficient due to re-computation of paths for the same state.; Prone to stack overflow for deep search paths without aggressive pruning.; Does not guarantee finding the shortest path first; it must explore the entire search space to find the minimum.; Can easily get stuck in infinite loops if cycles are not handled correctly.
### Explanation
The brute-force Depth First Search (DFS) approach tries to find a solution by exploring every possible path from the starting position. A recursive function is defined to navigate through the state space, where a state is defined by the bug's current position and whether the last jump was backward.

To prevent infinite loops (e.g., `0 -> a -> 0 -> a ...`), we must keep track of the states visited along the current path. A major drawback is that this method will explore paths exhaustively. For instance, it might find a very long path to the solution first and will only find the shortest path after exploring many other (potentially shorter) paths. This leads to a very high time complexity, making it unsuitable for the given constraints.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    int minJumps = Integer.MAX_VALUE;
    Set<Integer> forbiddenSet;
    int a, b, x;
    int limit;

    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        this.forbiddenSet = new HashSet<>();
        int maxForbidden = 0;
        for (int f : forbidden) {
            this.forbiddenSet.add(f);
            maxForbidden = Math.max(maxForbidden, f);
        }
        this.a = a;
        this.b = b;
        this.x = x;
        // A loose upper bound to prune search space
        this.limit = Math.max(x, maxForbidden) + a + b;

        // pathVisited stores "pos,isBackward" strings
        dfs(0, 0, false, new HashSet<String>());

        return minJumps == Integer.MAX_VALUE ? -1 : minJumps;
    }

    private void dfs(int pos, int jumps, boolean isLastBackward, Set<String> pathVisited) {
        if (pos == x) {
            minJumps = Math.min(minJumps, jumps);
            return;
        }

        // Pruning conditions
        if (pos < 0 || pos > limit || forbiddenSet.contains(pos) || jumps >= minJumps) {
            return;
        }

        String state = pos + "," + isLastBackward;
        if (pathVisited.contains(state)) {
            return; // Cycle detected in current path
        }

        pathVisited.add(state);

        // Forward jump
        dfs(pos + a, jumps + 1, false, pathVisited);

        // Backward jump
        if (!isLastBackward) {
            dfs(pos - b, jumps + 1, true, pathVisited);
        }

        pathVisited.remove(state); // Backtrack
    }
}
```
### Algorithm
*   Define a recursive function, say `dfs(position, jumps, isLastJumpBackward, pathVisited)`. 
*   `pathVisited` is a set of states `(position, isLastJumpBackward)` visited in the current recursive path to detect cycles.
*   The main function initializes a global minimum jumps variable, `minJumps`, to infinity and calls `dfs(0, 0, false, new HashSet<>())`.
*   Inside `dfs`:
    *   If the current number of `jumps` is already greater than or equal to `minJumps`, prune the search by returning.
    *   If `position == x`, a path is found. Update `minJumps = min(minJumps, jumps)` and return.
    *   Check for invalid states: if `position` is negative, forbidden, too far, or the state `(position, isLastJumpBackward)` is already in `pathVisited`, return to avoid cycles and invalid moves.
    *   Add the current state to `pathVisited` to mark it as part of the current path.
    *   Recursively call for the next possible moves:
        *   Forward jump: `dfs(position + a, jumps + 1, false, pathVisited)`.
        *   Backward jump: If `isLastJumpBackward` is false, `dfs(position - b, jumps + 1, true, pathVisited)`.
    *   Backtrack by removing the current state from `pathVisited` before returning.
*   After the initial call returns, if `minJumps` is still infinity, it means `x` is unreachable. Otherwise, `minJumps` holds the answer.

## Breadth-First Search (BFS) on State Graph
This problem can be modeled as finding the shortest path in an unweighted graph. Breadth-First Search (BFS) is the perfect algorithm for this task. We treat each possible state of the bug—its position and whether its last jump was backward—as a node in a graph. A jump represents an edge. BFS explores the graph layer by layer, guaranteeing that the first time it reaches the target position `x`, it does so via the minimum number of jumps.
**Time:** O(max(x, max_f) + a + b). Each state `(position, was_backward)` is visited at most once. The number of states is proportional to the search limit. · **Space:** O(max(x, max_f) + a + b), where `max_f` is the maximum forbidden position. This space is used for the `visited` array and the queue.
**Pros:** Guaranteed to find the shortest path in terms of number of jumps.; Efficient and avoids re-computing states by using a `visited` set.; Completes within the time limits for the given constraints.
**Cons:** Requires careful determination of the search space boundary to be both correct and efficient.; Uses more memory than DFS for wide search graphs, although this is not an issue with the given constraints.
### Explanation
The key insight is to represent the problem as a shortest path problem on a state graph. A state is defined by a pair: `(position, was_last_jump_backward)`. The `was_last_jump_backward` flag is crucial because it determines whether a backward jump is allowed from the current position.

We start a BFS from the initial state `(0, false)`. A queue stores the states to be visited. To avoid infinite loops and redundant work, we use a `visited` data structure (e.g., a 2D boolean array) to keep track of states we've already processed. The BFS proceeds in levels, where each level corresponds to one jump. When we first encounter the target position `x`, we are guaranteed to have found a path with the minimum number of jumps because BFS explores all paths of length `k` before exploring any path of length `k+1`.

An important consideration is the search space boundary. The bug can jump beyond `x`. We need to define a reasonable upper limit for positions to explore. A safe and effective limit is `max(x, max(forbidden)) + a + b`, which is well within the limits imposed by the problem constraints.

```java
import java.util.*;

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        if (x == 0) {
            return 0;
        }

        Set<Integer> forbiddenSet = new HashSet<>();
        int maxVal = x;
        for (int f : forbidden) {
            forbiddenSet.add(f);
            maxVal = Math.max(maxVal, f);
        }

        // A safe upper bound for position to explore.
        int limit = maxVal + a + b;

        Queue<int[]> queue = new LinkedList<>();
        // State: {position, isLastJumpBackward} (0 for false, 1 for true)
        queue.offer(new int[]{0, 0});

        // visited[position][isLastJumpBackward]
        boolean[][] visited = new boolean[limit + 1][2];
        visited[0][0] = true;

        int jumps = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] current = queue.poll();
                int pos = current[0];
                int lastWasBackward = current[1];

                if (pos == x) {
                    return jumps;
                }

                // Try forward jump
                int forwardPos = pos + a;
                if (forwardPos <= limit && !visited[forwardPos][0] && !forbiddenSet.contains(forwardPos)) {
                    visited[forwardPos][0] = true;
                    queue.offer(new int[]{forwardPos, 0});
                }

                // Try backward jump (only if last jump was not backward)
                if (lastWasBackward == 0) {
                    int backwardPos = pos - b;
                    if (backwardPos >= 0 && !visited[backwardPos][1] && !forbiddenSet.contains(backwardPos)) {
                        visited[backwardPos][1] = true;
                        queue.offer(new int[]{backwardPos, 1});
                    }
                }
            }
            jumps++;
        }

        return -1;
    }
}
```
### Algorithm
*   Initialize a `Set` with all `forbidden` positions for O(1) lookups.
*   Determine a safe upper bound for the search space. A value like `max(x, max(forbidden)) + a + b` is sufficient to ensure we don't miss any potential solutions.
*   Initialize a queue for BFS and add the starting state `(position=0, lastJumpWasBackward=false)`.
*   Use a 2D boolean array `visited[position][wasBackward]` to keep track of visited states to avoid redundant computations and cycles.
*   Start the BFS loop, proceeding level by level. Each level corresponds to one additional jump.
*   In each level, dequeue all states added in the previous level.
*   For each dequeued state `(pos, lastWasBackward)`:
    *   If `pos == x`, the shortest path is found. Return the current jump count.
    *   Explore the **forward jump**: Calculate `nextPos = pos + a`. If `nextPos` is within the bounds, not forbidden, and the state `(nextPos, false)` has not been visited, add it to the queue and mark it as visited.
    *   Explore the **backward jump**: If `lastWasBackward` is false, calculate `nextPos = pos - b`. If `nextPos` is non-negative, not forbidden, and the state `(nextPos, true)` has not been visited, add it to the queue and mark it as visited.
*   If the queue becomes empty and `x` has not been reached, it's impossible to get home. Return -1.

# Solutions
### Java

```java
class Solution { public int minimumJumps ( int [] forbidden , int a , int b , int x ) { Set < Integer > s = new HashSet <>(); for ( int v : forbidden ) { s . add ( v ); } Deque < int []> q = new ArrayDeque <>(); q . offer ( new int [] { 0 , 1 }); final int n = 6000 ; boolean [][] vis = new boolean [ n ][ 2 ]; vis [ 0 ][ 1 ] = true ; for ( int ans = 0 ; ! q . isEmpty (); ++ ans ) { for ( int t = q . size (); t > 0 ; -- t ) { var p = q . poll (); int i = p [ 0 ], k = p [ 1 ]; if ( i == x ) { return ans ; } List < int []> nxt = new ArrayList <>(); nxt . add ( new int [] { i + a , 1 }); if (( k & 1 ) == 1 ) { nxt . add ( new int [] { i - b , 0 }); } for ( var e : nxt ) { int j = e [ 0 ]; k = e [ 1 ]; if ( j >= 0 && j < n && ! s . contains ( j ) && ! vis [ j ][ k ]) { q . offer ( new int [] { j , k }); vis [ j ][ k ] = true ; } } } } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int minimumJumps ( vector < int >& forbidden , int a , int b , int x ) { unordered_set < int > s ( forbidden . begin (), forbidden . end ()); queue < pair < int , int >> q ; q . emplace ( 0 , 1 ); const int n = 6000 ; bool vis [ n ][ 2 ]; memset ( vis , false , sizeof ( vis )); vis [ 0 ][ 1 ] = true ; for ( int ans = 0 ; q . size (); ++ ans ) { for ( int t = q . size (); t ; -- t ) { auto [ i , k ] = q . front (); q . pop (); if ( i == x ) { return ans ; } vector < pair < int , int >> nxts = { { i + a , 1 } }; if ( k & 1 ) { nxts . emplace_back ( i - b , 0 ); } for ( auto [ j , l ] : nxts ) { if ( j >= 0 && j < n && ! s . count ( j ) && ! vis [ j ][ l ]) { vis [ j ][ l ] = true ; q . emplace ( j , l ); } } } } return - 1 ; } };
```

### Python

```python
class Solution : def minimumJumps ( self , forbidden : List [ int ], a : int , b : int , x : int ) -> int : s = set ( forbidden ) q = deque ([( 0 , 1 )]) vis = {( 0 , 1 )} ans = 0 while q : for _ in range ( len ( q )): i , k = q . popleft () if i == x : return ans nxt = [( i + a , 1 )] if k & 1 : nxt . append (( i - b , 0 )) for j , k in nxt : if 0 <= j < 6000 and j not in s and ( j , k ) not in vis : q . append (( j , k )) vis . add (( j , k )) ans += 1 return - 1
```