# Frog Position After T Seconds
**Difficulty:** HARD
[External](https://leetcode.com/problems/frog-position-after-t-seconds)
Canonical: https://scaleengineer.com/dsa/problems/frog-position-after-t-seconds
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Graph
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/frog-position-after-t-seconds/image0.jpg) 

**Input:** n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
**Output:** 0.16666666666666666 
**Explanation:** The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after **second 1** and then jumping with 1/2 probability to vertex 4 after **second 2**. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666. 

**Example 2:**

**![](https://assets.glich.co/dsa/frog-position-after-t-seconds/image1.jpg)** 

**Input:** n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
**Output:** 0.3333333333333333
**Explanation:** The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after **second 1**. 

**Constraints:**

* `1 <= n <= 100`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `1 <= ai, bi <= n`
* `1 <= t <= 50`
* `1 <= target <= n`

# Approaches
## Naive Simulation using BFS
This approach simulates the frog's movement second by second using a Breadth-First Search (BFS). However, it forgoes the use of an efficient graph representation like an adjacency list. At each step, to find the possible next positions for a frog at a vertex `u`, it iterates through the entire `edges` list. This leads to a less efficient implementation.
**Time:** O(t * N * E), where `N` is the number of vertices and `E` is the number of edges. Since `E = N-1`, this is `O(t * N^2)`. For each of the `t` seconds, we might process up to `N` nodes, and for each node, we scan all `E` edges to find its neighbors. · **Space:** O(N) for the `prob` array, `visited` array, and the BFS queue.
**Pros:** Conceptually simple simulation that directly models the problem statement.
**Cons:** Inefficient due to the repeated scanning of the `edges` list, leading to a quadratic time complexity.
### Explanation
We use a queue to keep track of the frog's possible locations and their associated probabilities. The state in the queue can be `(vertex, probability)`. We also use a `visited` array to ensure the frog only jumps to unvisited vertices. The simulation proceeds in time steps from `0` to `t`. In each time step, we process all the frog's possible locations from the previous second. For each location `u` with probability `p`, we find its unvisited neighbors by scanning the `edges` array. The probability `p` is then evenly distributed among these unvisited neighbors. These new states `(neighbor, p / num_neighbors)` are added to the queue for the next time step. If a frog at `u` has no unvisited neighbors, it gets "stuck". Its probability is recorded, and it's not processed further. After `t` seconds, the probability associated with the `target` vertex is the answer.

```java
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1) return 1.0;
        double[] prob = new double[n + 1];
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        prob[1] = 1.0;
        visited[1] = true;
        queue.offer(1);

        int time = 0;
        while (!queue.isEmpty() && time < t) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int u = queue.poll();
                
                List<Integer> neighbors = new ArrayList<>();
                for (int[] edge : edges) {
                    if (edge[0] == u) neighbors.add(edge[1]);
                    else if (edge[1] == u) neighbors.add(edge[0]);
                }

                int unvisitedNeighbors = 0;
                for (int neighbor : neighbors) {
                    if (!visited[neighbor]) {
                        unvisitedNeighbors++;
                    }
                }

                if (unvisitedNeighbors > 0) {
                    for (int neighbor : neighbors) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.offer(neighbor);
                            prob[neighbor] = prob[u] / unvisitedNeighbors;
                        }
                    }
                    prob[u] = 0; // Frog jumps away
                }
            }
            time++;
        }
        return prob[target];
    }
}
```
### Algorithm
*   Initialize a `prob` array to store probabilities, with `prob[1] = 1.0`.
*   Initialize a `visited` array and a queue for BFS, starting with vertex 1.
*   Loop for `time` from 0 to `t-1`.
*   In each time step, process all nodes currently in the queue (representing positions at that time).
*   For each vertex `u`, find its neighbors by iterating through the `edges` array.
*   Count the number of `unvisited` neighbors.
*   If there are unvisited neighbors, distribute `prob[u]` among them, update their probabilities, mark them as visited, and add them to the queue. Set `prob[u]` to 0 as the frog moves.
*   If there are no unvisited neighbors, the frog stays at `u`, so its probability is unchanged.
*   After the simulation, `prob[target]` holds the final answer.

## Depth-First Search
This approach uses a single Depth-First Search (DFS) traversal starting from the root (vertex 1) to determine the probability and time of arrival for the frog at the target vertex. The core idea is to traverse the tree and, for each node, calculate the probability of the frog reaching it and the time taken. After the traversal, we use this information to evaluate the final condition for the target vertex.
**Time:** O(N), where `N` is the number of vertices. We build an adjacency list in `O(N)` and then perform a single DFS traversal, visiting each vertex and edge once. · **Space:** O(N) for the adjacency list, the `visited` array, and the recursion stack in the worst case (a skewed tree).
**Pros:** Efficient O(N) solution.; Logically follows the single path of the frog to the target.
**Cons:** The recursive nature can be slightly less intuitive than a direct time-step simulation.; The base cases and conditions for updating the final probability need careful handling.
### Explanation
First, we build an adjacency list from the `edges` array for efficient neighbor lookups. We use a recursive DFS function, say `dfs(u, time, probability, visited)`, to explore the tree. The DFS starts from `dfs(1, 0, 1.0, visited)`. The `visited` array ensures the frog doesn't jump backward. During the traversal, we keep track of the probability of reaching the current node `u` and the time `time` it took. The key condition is evaluated when the DFS reaches the `target` node. If the frog reaches the `target` at time `k`: if `k == t`, this is a valid scenario. If `k < t`, it's only valid if the `target` node is a leaf in the traversal context (i.e., has no other unvisited children to jump to). Otherwise, the frog would have jumped away. If `k > t`, it's impossible to reach the target in time. The DFS function finds the single valid path to the target and calculates the probability.

```java
class Solution {
    List<Integer>[] adj;
    int target;
    int t;
    double targetProb = 0.0;

    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1) return 1.0;
        this.adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        this.target = target;
        this.t = t;
        
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        dfs(1, 0, 1.0, visited);
        return targetProb;
    }

    private void dfs(int u, int time, double prob, boolean[] visited) {
        int unvisitedNeighbors = 0;
        for (int v : adj[u]) {
            if (!visited[v]) {
                unvisitedNeighbors++;
            }
        }

        if (u == target && (time == t || unvisitedNeighbors == 0)) {
            targetProb = prob;
            return;
        }
        
        if (time >= t) {
            return;
        }

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dfs(v, time + 1, prob / unvisitedNeighbors, visited);
            }
        }
    }
}
```
### Algorithm
*   Build an adjacency list representation of the tree.
*   Create a `visited` array to track visited nodes.
*   Define a recursive DFS function `dfs(u, time, prob, visited)`.
*   Start the traversal from the root: `dfs(1, 0, 1.0, visited)` after marking 1 as visited.
*   In `dfs(u, ...)`:
    a. Count the number of unvisited neighbors (`num_children`).
    b. Check if `u` is the `target`. If it is, and either `time == t` or `num_children == 0`, we've found the answer. Store `prob` in a result variable and terminate this path.
    c. If `time >= t`, terminate this path.
    d. For each unvisited neighbor `v`, mark it as visited and recursively call `dfs(v, time + 1, prob / num_children, visited)`.

## Breadth-First Search Simulation
This is the most direct and arguably most intuitive approach. It uses Breadth-First Search (BFS) to simulate the frog's movement, where each level of the BFS corresponds to one second of time. This method keeps track of the probability distribution of the frog's location at each second.
**Time:** O(N), where `N` is the number of vertices. Building the adjacency list is `O(N)`. The BFS traversal visits each vertex and edge at most once. · **Space:** O(N) for the adjacency list, `prob` and `visited` arrays, and the queue which can hold up to `O(N)` vertices in the worst case.
**Pros:** Highly efficient with O(N) time complexity.; The iterative nature avoids recursion depth issues.; The level-by-level processing maps directly to the time steps in the problem, making the logic very clear.
**Cons:** No significant cons for the given constraints. It's an optimal solution.
### Explanation
We start by building an adjacency list for the tree to allow for efficient lookup of a node's neighbors. We use a queue to manage the BFS, storing each vertex the frog could be on. We also maintain an array, `probabilities`, to store the current probability of the frog being at any given vertex. We initialize `probabilities[1] = 1.0`. The simulation runs for `t` seconds. In each second (i.e., each level of the BFS), we process all vertices the frog could be on. For a vertex `u` with probability `p`, we find its unvisited neighbors. Let's say there are `k` such neighbors. If `k > 0`, the frog jumps. The probability `p` is divided equally among the `k` neighbors. We update their probabilities to `p/k` and add them to the queue for the next time step. The probability of staying at `u` becomes 0. If `k == 0`, the frog is at a leaf (or a node with all neighbors visited) and stays there forever. Its probability `p` remains, and we don't need to process it further. After `t` seconds, the value in `probabilities[target]` is the final answer.

```java
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1) return 1.0;
        
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        double[] prob = new double[n + 1];
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        prob[1] = 1.0;
        visited[1] = true;
        queue.offer(1);

        int time = 0;
        while (!queue.isEmpty() && time < t) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int u = queue.poll();
                
                int unvisitedNeighbors = 0;
                for (int neighbor : adj[u]) {
                    if (!visited[neighbor]) {
                        unvisitedNeighbors++;
                    }
                }

                if (unvisitedNeighbors > 0) {
                    for (int neighbor : adj[u]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.offer(neighbor);
                            prob[neighbor] = prob[u] / unvisitedNeighbors;
                        }
                    }
                    prob[u] = 0; // Frog jumps away
                }
            }
            time++;
        }
        
        return prob[target];
    }
}
```
### Algorithm
*   Build an adjacency list for the tree.
*   Initialize a `prob` array with `prob[1] = 1.0`.
*   Initialize a `visited` array and a queue for BFS, starting with vertex 1.
*   Loop for `time` from 0 to `t-1`.
*   In each iteration, process one level of the BFS. Get the current queue size.
*   Dequeue each vertex `u` from the current level.
*   Count its unvisited neighbors (`num_children`).
*   If `num_children > 0`, update the probabilities of the children to `prob[u] / num_children`, mark them visited, and enqueue them. Set `prob[u]` to 0.
*   If `num_children == 0`, do nothing; the frog stays at `u` with `prob[u]`.
*   After the loop, return `prob[target]`.

# Solutions
### CSharp

```csharp
public class Solution { public double FrogPosition ( int n , int [][] edges , int t , int target ) { List < int >[] g = new List < int >[ n + 1 ]; for ( int i = 0 ; i < n + 1 ; i ++) { g [ i ] = new List < int >(); } foreach ( int [] e in edges ) { int u = e [ 0 ], v = e [ 1 ]; g [ u ]. Add ( v ); g [ v ]. Add ( u ); } Queue < Tuple < int , double >> q = new Queue < Tuple < int , double >>(); q . Enqueue ( new Tuple < int , double >( 1 , 1.0 )); bool [] vis = new bool [ n + 1 ]; vis [ 1 ] = true ; for (; q . Count > 0 && t >= 0 ; -- t ) { for ( int k = q . Count ; k > 0 ; -- k ) { ( var u , var p ) = q . Dequeue (); int cnt = g [ u ]. Count - ( u == 1 ? 0 : 1 ); if ( u == target ) { return cnt * t == 0 ? p : 0 ; } foreach ( int v in g [ u ]) { if (! vis [ v ]) { vis [ v ] = true ; q . Enqueue ( new Tuple < int , double >( v , p / cnt )); } } } } return 0 ; } }
```

### Java

```java
class Solution {
public
  double frogPosition(int n, int[][] edges, int t, int target) {
    List<Integer>[] g = new List[n + 1];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int u = e[0], v = e[1];
      g[u].add(v);
      g[v].add(u);
    }
    Deque<Pair<Integer, Double>> q = new ArrayDeque<>();
    q.offer(new Pair<>(1, 1.0));
    boolean[] vis = new boolean[n + 1];
    vis[1] = true;
    for (; !q.isEmpty() && t >= 0; --t) {
      for (int k = q.size(); k > 0; --k) {
        var x = q.poll();
        int u = x.getKey();
        double p = x.getValue();
        int cnt = g[u].size() - (u == 1 ? 0 : 1);
        if (u == target) {
          return cnt * t == 0 ? p : 0;
        }
        for (int v : g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            q.offer(new Pair<>(v, p / cnt));
          }
        }
      }
    }
    return 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double frogPosition(int n, vector<vector<int>> &edges, int t, int target) {
    vector<vector<int>> g(n + 1);
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      g[u].push_back(v);
      g[v].push_back(u);
    }
    queue<pair<int, double>> q{{{1, 1.0}}};
    bool vis[n + 1];
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    for (; q.size() && t >= 0; --t) {
      for (int k = q.size(); k; --k) {
        auto [u, p] = q.front();
        q.pop();
        int cnt = g[u].size() - (u != 1);
        if (u == target) {
          return cnt * t == 0 ? p : 0;
        }
        for (int v : g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            q.push({v, p / cnt});
          }
        }
      }
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float: g = defaultdict(list) for u, v in edges: g[u]. append(v) g[v]. append(u) q = deque([(1, 1.0)]) vis = [False] * (n + 1) vis[1] = True while q and t >= 0: for _ in range(len(q)): u, p = q . popleft() cnt = len(g[u]) - int(u != 1) if u == target: return p if cnt * t == 0 else 0 for v in g[u]: if not vis[v]: vis[v] = True q . append((v, p / cnt)) t -= 1 return 0

```