Frog Position After T Seconds
HardPrompt
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:
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:
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 <= 100edges.length == n - 1edges[i].length == 21 <= ai, bi <= n1 <= t <= 501 <= target <= n
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
probarray to store probabilities, withprob[1] = 1.0. - Initialize a
visitedarray and a queue for BFS, starting with vertex 1. - Loop for
timefrom 0 tot-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 theedgesarray. - Count the number of
unvisitedneighbors. - If there are unvisited neighbors, distribute
prob[u]among them, update their probabilities, mark them as visited, and add them to the queue. Setprob[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.
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
Pros
Conceptually simple simulation that directly models the problem statement.
Cons
Inefficient due to the repeated scanning of the
edgeslist, leading to a quadratic time complexity.
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.
Algorithm
- Build an adjacency list representation of the tree.
- Create a
visitedarray 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 ifuis thetarget. If it is, and eithertime == tornum_children == 0, we've found the answer. Storeprobin a result variable and terminate this path. c. Iftime >= t, terminate this path. d. For each unvisited neighborv, mark it as visited and recursively calldfs(v, time + 1, prob / num_children, visited).
Walkthrough
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.
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); } } }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Build an adjacency list for the tree.
- Initialize a
probarray withprob[1] = 1.0. - Initialize a
visitedarray and a queue for BFS, starting with vertex 1. - Loop for
timefrom 0 tot-1. - In each iteration, process one level of the BFS. Get the current queue size.
- Dequeue each vertex
ufrom the current level. - Count its unvisited neighbors (
num_children). - If
num_children > 0, update the probabilities of the children toprob[u] / num_children, mark them visited, and enqueue them. Setprob[u]to 0. - If
num_children == 0, do nothing; the frog stays atuwithprob[u]. - After the loop, return
prob[target].
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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; }}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; }};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 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.