Practice/Meta/Leetcode 1377. Frog Position After T Seconds

Leetcode 1377. Frog Position After T Seconds

CodingOptional

Problem

You are given an undirected tree with n nodes numbered from 1 to n. The tree is rooted at node 1. You are also given an array edges where each element [a, b] represents a bidirectional edge between nodes a and b.

A frog starts at node 1 and performs a random walk following these rules:

• At each second, the frog looks at all unvisited neighboring nodes (nodes it hasn't been to yet).
• If there are unvisited neighbors, the frog jumps to one of them with equal probability.
• If there are no unvisited neighbors, the frog stays at its current node forever.
• The frog never backtracks to previously visited nodes.

Given a target node and a time limit t seconds, calculate the probability that the frog will be at the target node after exactly t seconds.

Return the probability as a floating-point number.

Requirements

1. Build the tree structure from the given edges
2. Simulate the frog's probabilistic movement from node 1
3. Account for branching factors at each node (number of unvisited neighbors)
4. Handle the case where the frog reaches a leaf node and must stay there
5. Calculate the exact probability of being at the target after t seconds

Constraints

• 1 <= n <= 100
• edges.length == n - 1
• edges[i].length == 2
• 1 <= edges[i][0], edges[i][1] <= n
• 1 <= t <= 50
• 1 <= target <= n
• The input represents a valid tree

Examples

Example 1:

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 frog starts at node 1. It has 3 neighbors (2, 3, 7), so probability 1/3 to go to node 2. From node 2, it has 2 unvisited neighbors (4, 6), so probability 1/2 to go to node 4. Total probability: (1/3) * (1/2) = 1/6 ≈ 0.1667

Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 1 Output: 0.0 Explanation: The frog must leave node 1 in the first second since it has unvisited neighbors. It cannot be at node 1 after exactly 1 second.

Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6 Output: 0.16666666666666666 Explanation: Node 6 is reached in 2 seconds with probability 1/6. Since node 6 is a leaf, the frog stays there for the remaining 18 seconds. The probability remains 1/6.