LeetCode 1377 - Frog Position After T Seconds

LeetCode Problem 1377

Difficulty: 🔴 Hard
Topics: Tree, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

This problem describes a frog moving through an undirected tree. A tree is a connected graph with no cycles, which means there is exactly one path between any two vertices.

The frog always starts at node 1. Every second, the frog must jump to one of its unvisited neighboring nodes. If there are multiple valid choices, each one is chosen with equal probability. Once a node has been visited, the frog can never return to it because the movement rule only allows jumps to unvisited vertices.

If the frog reaches a node where all neighbors have already been visited, then it becomes stuck and remains on that node forever.

The input consists of:

• n, the number of vertices
• edges, the list of undirected connections between vertices
• t, the number of seconds that pass
• target, the node whose probability we want to compute

The goal is to return the probability that after exactly t seconds, the frog is standing on target.

The constraints are relatively small:

• n <= 100
• t <= 50

These limits tell us that we do not need advanced optimizations. A straightforward graph traversal such as DFS or BFS is sufficient.

Several edge cases are important:

• The target might be reached before t seconds.
• The target might still have unvisited neighbors when reached.
• The target might be a leaf node.
• The frog may become stuck before time runs out.
• The target may never be reachable at exactly time t.

A common source of bugs is misunderstanding what happens when the frog reaches the target early. If the target still has unvisited neighbors, the frog must continue moving away from it in later seconds, so the probability becomes zero unless t exactly matches the arrival time. However, if the target is a leaf, the frog stays there forever once it arrives.

Approaches

Brute Force Approach

A brute force solution would simulate every possible path the frog can take.

Starting from node 1, at every second we recursively branch into all valid unvisited neighbors. For each path, we compute the probability contribution by multiplying by 1 / choices at every step. After exactly t seconds, we check whether the frog is at the target.

This approach is correct because it explicitly enumerates every valid movement sequence and accumulates probabilities accurately.

However, this method becomes inefficient because the number of possible paths grows exponentially with depth. Even though the constraints are not enormous, unnecessary recomputation makes this approach less elegant and harder to reason about.

Optimal Approach

The key observation is that the graph is a tree.

Because a tree has exactly one path between any two nodes, the frog can only reach the target through one unique route. We do not need to explore arbitrary cycles or revisit states.

We can perform a DFS or BFS traversal while tracking:

• Current node
• Current time
• Current probability
• Parent node, to avoid revisiting

At every node:

• Count how many unvisited neighbors exist.
• Divide the current probability equally among them.
• Continue traversal.

The important logic occurs when we reach the target:

• If we arrive exactly at time t, return the current probability.
• If we arrive before t and the target is a leaf, the frog stays there forever, so return the probability.
• If we arrive before t but the target has unvisited neighbors, the frog must leave, so return 0.

Since each edge and node is visited only once, the algorithm is linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(branching^t)	O(t)	Explores every possible movement sequence
Optimal	O(n)	O(n)	DFS/BFS traversal using tree properties

Algorithm Walkthrough

1. Build an adjacency list from the edge list.

Since the graph is undirected, every edge [u, v] must be added in both directions. An adjacency list allows efficient neighbor lookup during traversal. 2. Start a DFS from node 1.

The DFS keeps track of:

• Current node
• Parent node
• Current time elapsed
• Current probability

The parent is necessary because the frog cannot revisit already visited nodes. 3. Count the number of valid next moves.

For the current node, valid moves are neighbors excluding the parent node. This represents all unvisited neighbors. 4. Check whether the current node is the target.

There are two valid situations where the frog can remain at the target:

• We arrive exactly at time t
• We arrive earlier than t, but the target has no unvisited neighbors

Otherwise, the frog must continue moving away, so the probability becomes zero. 5. Distribute probability among children.

If the node has k valid next moves, then each child receives:

$$\text{next probability} = \frac{\text{current probability}}{k}$$

Continue DFS recursively for each child. 6. Return the probability once the target is found.

Because the graph is a tree, only one path can lead to the target.

Why it works

The algorithm works because trees contain exactly one simple path between nodes. The frog's movement is completely determined by the available unvisited neighbors at each step. By recursively distributing probability equally among all valid children, we model the random process exactly. The stopping condition correctly handles the special rule that the frog remains at a node forever once no unvisited neighbors exist.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def frogPosition(
        self,
        n: int,
        edges: List[List[int]],
        t: int,
        target: int
    ) -> float:
        
        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node: int, parent: int, time: int, probability: float) -> float:
            children = 0

            for neighbor in graph[node]:
                if neighbor != parent:
                    children += 1

            # If we reached the target
            if node == target:
                # Valid if:
                # 1. exact time match
                # 2. no further moves available
                if time == t or (children == 0 and time < t):
                    return probability
                return 0.0

            # No more time left
            if time == t:
                return 0.0

            next_probability = probability / children

            for neighbor in graph[node]:
                if neighbor != parent:
                    result = dfs(
                        neighbor,
                        node,
                        time + 1,
                        next_probability
                    )

                    if result > 0:
                        return result

            return 0.0

        return dfs(1, 0, 0, 1.0)

The implementation begins by constructing the adjacency list representation of the tree. Since the graph is undirected, every edge is inserted in both directions.

The DFS function is responsible for exploring the tree while tracking time and probability. The parent parameter prevents revisiting nodes, which matches the problem requirement that the frog cannot jump to already visited vertices.

For each node, we count the number of valid children. This value determines how probability is divided among possible moves.

The most important logic occurs when the current node equals the target. The code carefully checks whether the frog is allowed to remain there at the current time. If the target still has unvisited neighbors and time remains, the frog must continue moving, so the probability becomes zero.

The DFS eventually returns the probability of the unique valid path leading to the target.

Go Solution

package main

func frogPosition(n int, edges [][]int, t int, target int) float64 {
	graph := make([][]int, n+1)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	var dfs func(node, parent, time int, probability float64) float64

	dfs = func(node, parent, time int, probability float64) float64 {
		children := 0

		for _, neighbor := range graph[node] {
			if neighbor != parent {
				children++
			}
		}

		// Reached target
		if node == target {
			if time == t || (children == 0 && time < t) {
				return probability
			}
			return 0.0
		}

		// No time left
		if time == t {
			return 0.0
		}

		nextProbability := probability / float64(children)

		for _, neighbor := range graph[node] {
			if neighbor != parent {
				result := dfs(
					neighbor,
					node,
					time+1,
					nextProbability,
				)

				if result > 0 {
					return result
				}
			}
		}

		return 0.0
	}

	return dfs(1, 0, 0, 1.0)
}

The Go implementation closely mirrors the Python version. The adjacency list is implemented using a slice of integer slices.

One important difference is explicit type conversion when dividing probabilities. Since children is an integer, it must be converted to float64 before division.

Go also requires the recursive DFS function to be declared using a variable assignment before definition so the function can reference itself recursively.

Worked Examples

Example 1

Input:

n = 7
edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]
t = 2
target = 4

Constructed graph:

Node	Neighbors
1	2, 3, 7
2	1, 4, 6
3	1, 5
4	2
5	3
6	2
7	1

Initial state:

Node	Time	Probability
1	0	1.0

At node 1, there are 3 possible moves.

Each move gets probability:

$$\frac{1}{3}$$

Move to node 2:

Node	Time	Probability
2	1	1/3

At node 2, excluding parent 1, there are 2 children: 4 and 6.

Each receives:

$$\frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$$

Move to node 4:

Node	Time	Probability
4	2	1/6

We reached the target exactly at time 2.

Final answer:

$$\frac{1}{6} = 0.16666666666666666$$

Example 2

Input:

n = 7
edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]
t = 1
target = 7

Initial state:

Node	Time	Probability
1	0	1.0

At node 1, there are 3 possible moves.

Probability for each:

$$\frac{1}{3}$$

Move to node 7:

Node	Time	Probability
7	1	1/3

We reached the target exactly at time 1.

Final answer:

$$\frac{1}{3} = 0.3333333333333333$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node and edge is visited at most once
Space	O(n)	Adjacency list and recursion stack

The DFS traverses the tree once. Since a tree with n nodes contains exactly n - 1 edges, the total traversal cost is linear. The adjacency list stores all edges, and the recursion depth can reach at most n in a skewed tree.

Test Cases

from typing import List

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        from collections import defaultdict

        graph = defaultdict(list)

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node, parent, time, probability):
            children = 0

            for neighbor in graph[node]:
                if neighbor != parent:
                    children += 1

            if node == target:
                if time == t or (children == 0 and time < t):
                    return probability
                return 0.0

            if time == t:
                return 0.0

            next_probability = probability / children

            for neighbor in graph[node]:
                if neighbor != parent:
                    result = dfs(
                        neighbor,
                        node,
                        time + 1,
                        next_probability
                    )

                    if result > 0:
                        return result

            return 0.0

        return dfs(1, 0, 0, 1.0)

solution = Solution()

# Example 1
assert abs(
    solution.frogPosition(
        7,
        [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]],
        2,
        4
    ) - 0.16666666666666666
) < 1e-5  # standard example

# Example 2
assert abs(
    solution.frogPosition(
        7,
        [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]],
        1,
        7
    ) - 0.3333333333333333
) < 1e-5  # direct one-step jump

# Target is root and frog must move away
assert abs(
    solution.frogPosition(
        3,
        [[1,2],[1,3]],
        1,
        1
    ) - 0.0
) < 1e-5  # frog cannot stay at root

# Target is leaf reached early, frog stays there
assert abs(
    solution.frogPosition(
        2,
        [[1,2]],
        5,
        2
    ) - 1.0
) < 1e-5  # frog remains at leaf forever

# Target reached too early but must continue moving
assert abs(
    solution.frogPosition(
        3,
        [[1,2],[2,3]],
        1,
        2
    ) - 1.0
) < 1e-5  # exact arrival time

assert abs(
    solution.frogPosition(
        3,
        [[1,2],[2,3]],
        2,
        2
    ) - 0.0
) < 1e-5  # frog must leave node 2

# Single path tree
assert abs(
    solution.frogPosition(
        4,
        [[1,2],[2,3],[3,4]],
        3,
        4
    ) - 1.0
) < 1e-5  # deterministic movement

# Unreachable within given time
assert abs(
    solution.frogPosition(
        4,
        [[1,2],[1,3],[3,4]],
        1,
        4
    ) - 0.0
) < 1e-5  # target too far away

Test	Why
Example 1	Verifies multi-step probability splitting
Example 2	Verifies direct jump probability
Target is root	Ensures frog cannot remain if moves exist
Leaf reached early	Ensures frog stays forever at leaf
Exact arrival time	Verifies valid timing logic
Must continue moving	Ensures early arrival does not incorrectly count
Single path tree	Verifies deterministic traversal
Unreachable target	Ensures impossible states return zero

Edge Cases

One important edge case occurs when the target is reached before time t, but the target still has unvisited neighbors. In this situation, the frog is forced to continue moving away from the target. A buggy implementation might incorrectly return the probability immediately upon reaching the target. The solution avoids this by checking whether the target node has available children.

Another important case occurs when the target is a leaf node. Once the frog reaches a leaf, it remains there forever because no unvisited neighbors exist. The implementation correctly handles this by allowing the probability to remain valid even when time < t.

A third edge case is when the target is the starting node 1. If t > 0 and node 1 has neighbors, the frog must leave immediately. Therefore, the answer should be zero unless the graph consists of only one node. The DFS logic naturally handles this because the root's available children force movement away from node 1.

A final subtle case is a linear chain tree. In such trees, every move is deterministic because there is only one unvisited neighbor at each step. The probability should remain 1.0 throughout the traversal. Since the algorithm divides by the number of available children, and that value is always 1, the implementation handles this correctly.