Frog position after t seconds

Tree Depth-First Search Breadth-First Search Graph Theory

37.9% acceptance

Feb 25, 2026

841

151

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices, it jumps randomly to one of them with the same probability. Otherwise, when the frog can not jump to any unvisited vertex, it jumps forever on the same vertex. The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Return the probability that after t seconds the frog is on the vertex target. Answers within 10-5 of the actual answer will be accepted.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn frog_position(n: i32, edges: Vec<Vec<i32>>, t: i32, target: i32) -> f64 {
    let n = n as usize;
    let mut adj = vec![vec![]; n + 1];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }
    // BFS from node 1
    let mut prob = vec![0.0f64; n + 1];
    prob[1] = 1.0;
    let mut visited = vec![false; n + 1];
    visited[1] = true;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((1usize, 0i32));
    while let Some((node, time)) = queue.pop_front() {
      let unvisited: Vec<usize> = adj[node].iter()
        .filter(|&&nb| !visited[nb])
        .cloned().collect();
      let children = unvisited.len();
      if node == target as usize {
        // Check if frog stays here (no unvisited children or time exactly t)
        if children == 0 || time == t {
          return prob[node];
        }
        return 0.0;
      }
      for &nb in &unvisited {
        visited[nb] = true;
        prob[nb] = prob[node] / children as f64;
        if time + 1 <= t {
          queue.push_back((nb, time + 1));
        }
      }
    }
    0.0
  }
}