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.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6


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

Example 3

1
2
3
4
5
6
7


    
    
    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.

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

We need to find the minimum number of jumps to reach position x from 0, following the rules. BFS is ideal for finding the shortest path in such state-space problems, as it explores all possible moves level by level and avoids revisiting states.

Approach

  1. Use a queue to perform BFS, storing the current position, whether the last jump was backward, and the number of jumps.
  2. Use a set to mark forbidden positions and a 2D visited array to avoid revisiting states (position, last jump direction).
  3. For each state, try jumping forward and backward (if allowed), and enqueue new states if not forbidden or visited.
  4. Stop when reaching position x and return the number of jumps.
  5. If the queue is exhausted, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> forb(forbidden.begin(), forbidden.end());
        int bound = max(x, *max_element(forbidden.begin(), forbidden.end())) + a + b;
        vector<vector<bool>> vis(bound+1, vector<bool>(2));
        queue<tuple<int,int,int>> q;
        q.push({0,0,0});
        vis[0][0] = true;
        while (!q.empty()) {
            auto [pos, back, step] = q.front(); q.pop();
            if (pos == x) return step;
            int fwd = pos + a;
            if (fwd <= bound && !forb.count(fwd) && !vis[fwd][0]) {
                vis[fwd][0] = true;
                q.push({fwd, 0, step+1});
            }
            int bwd = pos - b;
            if (back == 0 && bwd >= 0 && !forb.count(bwd) && !vis[bwd][1]) {
                vis[bwd][1] = true;
                q.push({bwd, 1, step+1});
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func minimumJumps(forbidden []int, a, b, x int) int {
    forb := make(map[int]struct{})
    bound := x
    for _, v := range forbidden {
        forb[v] = struct{}{}
        if v > bound { bound = v }
    }
    bound += a + b
    vis := make([][2]bool, bound+1)
    type state struct{ pos, back, step int }
    q := []state{{0,0,0}}
    vis[0][0] = true
    for len(q) > 0 {
        s := q[0]; q = q[1:]
        if s.pos == x { return s.step }
        fwd := s.pos + a
        if fwd <= bound && !vis[fwd][0] {
            if _, ok := forb[fwd]; !ok {
                vis[fwd][0] = true
                q = append(q, state{fwd,0,s.step+1})
            }
        }
        bwd := s.pos - b
        if s.back == 0 && bwd >= 0 && !vis[bwd][1] {
            if _, ok := forb[bwd]; !ok {
                vis[bwd][1] = true
                q = append(q, state{bwd,1,s.step+1})
            }
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> forb = new HashSet<>();
        int bound = x;
        for (int v : forbidden) bound = Math.max(bound, v);
        bound += a + b;
        boolean[][] vis = new boolean[bound+1][2];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0,0});
        vis[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int pos = cur[0], back = cur[1], step = cur[2];
            if (pos == x) return step;
            int fwd = pos + a;
            if (fwd <= bound && !forb.contains(fwd) && !vis[fwd][0]) {
                vis[fwd][0] = true;
                q.offer(new int[]{fwd,0,step+1});
            }
            int bwd = pos - b;
            if (back == 0 && bwd >= 0 && !forb.contains(bwd) && !vis[bwd][1]) {
                vis[bwd][1] = true;
                q.offer(new int[]{bwd,1,step+1});
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun minimumJumps(forbidden: IntArray, a: Int, b: Int, x: Int): Int {
        val forb = forbidden.toSet()
        var bound = x
        for (v in forbidden) bound = maxOf(bound, v)
        bound += a + b
        val vis = Array(bound+1) { BooleanArray(2) }
        val q = ArrayDeque<Triple<Int,Int,Int>>()
        q.add(Triple(0,0,0))
        vis[0][0] = true
        while (q.isNotEmpty()) {
            val (pos, back, step) = q.removeFirst()
            if (pos == x) return step
            val fwd = pos + a
            if (fwd <= bound && !forb.contains(fwd) && !vis[fwd][0]) {
                vis[fwd][0] = true
                q.add(Triple(fwd,0,step+1))
            }
            val bwd = pos - b
            if (back == 0 && bwd >= 0 && !forb.contains(bwd) && !vis[bwd][1]) {
                vis[bwd][1] = true
                q.add(Triple(bwd,1,step+1))
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def minimum_jumps(forbidden: list[int], a: int, b: int, x: int) -> int:
    forb = set(forbidden)
    bound = max(x, max(forbidden, default=0)) + a + b
    from collections import deque
    vis = [[False, False] for _ in range(bound+1)]
    q = deque([(0, 0, 0)])
    vis[0][0] = True
    while q:
        pos, back, step = q.popleft()
        if pos == x:
            return step
        fwd = pos + a
        if fwd <= bound and not vis[fwd][0] and fwd not in forb:
            vis[fwd][0] = True
            q.append((fwd, 0, step+1))
        bwd = pos - b
        if back == 0 and bwd >= 0 and not vis[bwd][1] and bwd not in forb:
            vis[bwd][1] = True
            q.append((bwd, 1, step+1))
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn minimum_jumps(forbidden: Vec<i32>, a: i32, b: i32, x: i32) -> i32 {
        use std::collections::{HashSet, VecDeque};
        let forb: HashSet<_> = forbidden.into_iter().collect();
        let bound = forb.iter().max().copied().unwrap_or(0).max(x) + a + b;
        let mut vis = vec![[false; 2]; (bound+1) as usize];
        let mut q = VecDeque::new();
        q.push_back((0, 0, 0));
        vis[0][0] = true;
        while let Some((pos, back, step)) = q.pop_front() {
            if pos == x { return step; }
            let fwd = pos + a;
            if fwd <= bound && !forb.contains(&fwd) && !vis[fwd as usize][0] {
                vis[fwd as usize][0] = true;
                q.push_back((fwd, 0, step+1));
            }
            let bwd = pos - b;
            if back == 0 && bwd >= 0 && !forb.contains(&bwd) && !vis[bwd as usize][1] {
                vis[bwd as usize][1] = true;
                q.push_back((bwd, 1, step+1));
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    minimumJumps(forbidden: number[], a: number, b: number, x: number): number {
        const forb = new Set(forbidden);
        let bound = Math.max(x, ...forbidden) + a + b;
        const vis = Array.from({length: bound+1}, () => [false, false]);
        const q: [number, number, number][] = [[0, 0, 0]];
        vis[0][0] = true;
        while (q.length) {
            const [pos, back, step] = q.shift()!;
            if (pos === x) return step;
            const fwd = pos + a;
            if (fwd <= bound && !forb.has(fwd) && !vis[fwd][0]) {
                vis[fwd][0] = true;
                q.push([fwd, 0, step+1]);
            }
            const bwd = pos - b;
            if (back === 0 && bwd >= 0 && !forb.has(bwd) && !vis[bwd][1]) {
                vis[bwd][1] = true;
                q.push([bwd, 1, step+1]);
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(N), where N is the search space size. Each state is visited at most once.
  • 🧺 Space complexity: O(N), for the visited array and queue.