Frog jump

Array Dynamic Programming

47.1% acceptance

Jan 13, 2026

5970

276

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit. If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

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

impl Solution {
  pub fn can_cross(stones: Vec<i32>) -> bool {
    let stone_set: HashSet<i32> = stones.iter().cloned().collect();
    let target = stones[stones.len() - 1];
    let mut memo: HashMap<(i32, i32), bool> = HashMap::new();
    
    fn dfs(pos: i32, k: i32, target: i32, stones: &HashSet<i32>, memo: &mut HashMap<(i32, i32), bool>) -> bool {
      if pos == target {
        return true;
      }
      
      if let Some(&result) = memo.get(&(pos, k)) {
        return result;
      }
      
      for next_k in [k - 1, k, k + 1] {
        if next_k > 0 && stones.contains(&(pos + next_k)) {
          if dfs(pos + next_k, next_k, target, stones, memo) {
            memo.insert((pos, k), true);
            return true;
          }
        }
      }
      
      memo.insert((pos, k), false);
      false
    }
    
    dfs(0, 0, target, &stone_set, &mut memo)
  }
}