Minimum sideway jumps

Array Dynamic Programming Greedy

51.5% acceptance

Feb 25, 2026

1279

There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second lane and wants to jump to point n. You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane. Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0. Note: There will be no obstacles on points 0 and n.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_side_jumps(obstacles: Vec<i32>) -> i32 {
    // dp[i] = min side jumps to be at lane i+1 (0-indexed: lanes 0,1,2)
    let mut dp = [1i32, 0, 1]; // start at lane 1 (0-indexed), cost 0; others cost 1

    for i in 1..obstacles.len() {
      let obs = obstacles[i] as usize;
      // Block the obstacle lane
      if obs > 0 {
        dp[obs - 1] = i32::MAX / 2;
      }
      // Propagate min through side jumps
      let mn = dp.iter().copied().min().unwrap();
      for j in 0..3 {
        if obs > 0 && j == obs - 1 { continue; }
        if dp[j] > mn + 1 {
          dp[j] = mn + 1;
        }
      }
    }
    dp.iter().copied().min().unwrap()
  }
}