Minimum jumps to reach home

Array Hash Table Breadth-First Search

30.6% acceptance

Feb 25, 2026

1562

285

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 forbidden, a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If no possible sequence exists, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashSet, VecDeque};

impl Solution {
  pub fn minimum_jumps(forbidden: Vec<i32>, a: i32, b: i32, x: i32) -> i32 {
    let forbidden_set: HashSet<i32> = forbidden.into_iter().collect();
    // Upper bound: safe limit beyond which we never need to go
    let upper = 6000i32;
    // visited[pos][can_back]: true if visited
    let mut visited = vec![[false; 2]; (upper + 1) as usize];
    // BFS: (position, can_back_flag)
    // can_back: 1 = can jump backward, 0 = cannot
    let mut queue = VecDeque::new();
    // Start: can jump backward (last jump was "forward" or start)
    visited[0][1] = true;
    queue.push_back((0i32, 1usize, 0i32)); // (pos, can_back, steps)

    while let Some((pos, can_back, steps)) = queue.pop_front() {
      if pos == x {
        return steps;
      }
      // Forward jump
      let fwd = pos + a;
      if fwd <= upper && !forbidden_set.contains(&fwd) && !visited[fwd as usize][1] {
        visited[fwd as usize][1] = true;
        queue.push_back((fwd, 1, steps + 1));
      }
      // Backward jump (only if can_back and pos-b >= 0)
      if can_back == 1 {
        let bwd = pos - b;
        if bwd >= 0 && !forbidden_set.contains(&bwd) && !visited[bwd as usize][0] {
          visited[bwd as usize][0] = true;
          queue.push_back((bwd, 0, steps + 1));
        }
      }
    }
    -1
  }
}