Frog Position After T Seconds
Hard · Graphs · Tree · Depth-First Search · Breadth-First Search · Graph
Problem
An undirected tree has n vertices numbered 1 to n, described by edges, where edges[i] = [a, b]. A frog starts on vertex 1. Every second it jumps to one of the unvisited vertices next to its current vertex, choosing uniformly at random among them. It never jumps back to a vertex it has already visited. If there is no unvisited neighbor, the frog stays where it is forever.
Return the probability that the frog is on vertex target after exactly t seconds. Answers within 10^-5 of the true value are accepted.
Examples
Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]], t = 2, target = 4 Output: 0.25
It jumps to 2 with probability 1/2, then to 4 with probability 1/2.
Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]], t = 5, target = 3 Output: 0.5
Once on leaf 3 the frog stays there, so the answer is the chance of jumping to 3 first.
Input: n = 3, edges = [[1,2],[2,3]], t = 1, target = 3 Output: 0.0
After one second the frog is on vertex 2, not 3.
Constraints
- 1 <= n <= 100
- len(edges) == n - 1
- edges[i] == [a, b] with 1 <= a, b <= n, and the edges form a tree
- 1 <= t <= 50
- 1 <= target <= n
Approaches
- Simulate every second — time O(t · n), space O(n)
Follow-up
What if you were asked where the frog most likely is after t seconds? Compute every vertex’s probability in one search and compare them exactly (fractions), because ties are common. See the second use case.
Related problems
Start free on Cariara · Coding problems · System design studio
