Minimum Jumps to Reach Home

Share

A bug at position 0 can jump forward a or backward b. Some positions are forbidden. Find min jumps to reach x.

Example 1
Input: forbidden=[14,4,18,1,15], a=3, b=15, x=9 → Output: 3
Example 2
Input: forbidden=[8,3,16,6,12,20], a=15, b=13, x=11 → Output: -1

Solution Approach

BFS with states (position, lastJump). Bound search space to avoid infinite loops.

  • BFS with (position, direction) state
  • Bound max position to max(forbidden)+a+b+x
  • Track visited positions and last move direction
  • At each step try forward jump (always) and backward jump (if last was not backward)
  • Return steps when x reached
Java
public int minimumJumps(int[] forbidden, int a, int b, int x) {
    Set<Integer> banned = new HashSet<>();
    for (int f : forbidden) banned.add(f);
    int bound = Arrays.stream(forbidden).max().orElse(0) + a + b + x;
    Set<String> visited = new HashSet<>();
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0}); // {pos, lastDir: 0=none/fwd, 1=back}
    visited.add("0,0");
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size-- > 0) {
            int[] cur = queue.poll();
            int pos = cur[0], dir = cur[1];
            if (pos == x) return steps;
            int fwd = pos + a;
            if (fwd <= bound && !banned.contains(fwd) && visited.add(fwd + ",0"))
                queue.offer(new int[]{fwd, 0});
            if (dir != 1) {
                int bck = pos - b;
                if (bck >= 0 && !banned.contains(bck) && visited.add(bck + ",1"))
                    queue.offer(new int[]{bck, 1});
            }
        }
        steps++;
    }
    return -1;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)