1377. Frog Position After T Seconds

HardTreeDepth-First SearchBreadth-First SearchGraph
Leetcode Link

Problem Description

In this problem, we have a tree (a type of undirected graph with no cycles) consisting of n vertices numbered from 1 to n. There's a frog at vertex 1 that starts to jump from one vertex to another. The jumps occur every second and the frog can only jump to an unvisited vertex. It's also important to note that the frog cannot jump back to a visited vertex.

As the tree is undirected, we are given the edges that connect the vertices as an array where each element edges[i] = [ai, bi] signifies there's an edge between vertex ai and vertex bi. The objective is to calculate the probability that the frog is on a specific vertex (target) after t seconds.

One crucial rule to consider is the frog's jumping behavior:

  • If the frog has multiple unvisited vertices it can jump to, it will choose one at random, with each option having an equal chance.
  • If there are no unvisited vertices to jump to, the frog will stay at its current vertex indefinitely.

The solution requires us to return the probability that the frog is on the target vertex after exactly t seconds. It's worth noting that we consider an answer accurate if it's within 10^-5 of the actual answer.

Intuition

The strategy to solve this problem is via Breadth-First Search (BFS), which is a common algorithm used to traverse or search tree or graph data structures. BFS explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

The basic steps for BFS:

  • Start at the root node (vertex 1 in this case) and visit it.
  • Explore all the adjacent unvisited vertices and jump to them with equal probability.
  • Mark the visited vertices to prevent revisiting them.
  • Keep track of probabilities of reaching each vertex.
  • Continue this process until we reach t seconds or we have no more unvisited adjacent vertices to explore.

In the context of this problem, we're not just traversing the graph but also keeping track of the probability of reaching each vertex. We implement BFS with a queue to keep track of the vertices to visit and their corresponding probabilities (initialized with vertex 1 and probability 1.0):

  1. Mark the first vertex as visited.
  2. Use a while loop to process levels and decrement the remaining time t.
  3. At each second (or level in BFS), we check:
    • If the current vertex is the target and there are no more unvisited vertices to explore, we return the probability.
    • If the current vertex is the target but thereโ€™s still time left and no vertices to explore, the frog stays there, so the probability is 0 unless it's the last second.
  4. We loop through the adjacent vertices (children in the tree), marking them as visited, and enqueue them with the updated probability (divided by the number of unvisited children).
  5. Continue this until we run out of time t or the queue is empty.

The case where the frog reaches the target but can jump to other vertices is important: if there's time left but no moves are possible, the frog stays indefinitely on the target vertex, thus fulfilling our requirement.

This algorithm efficiently calculates the probability of the frog being at a certain vertex after t seconds by considering each possible jump at every second, ensuring that all routes and their probabilities are correctly accounted for.

Learn more about Tree, Depth-First Search, Breadth-First Search and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Solution Approach

The solution to this problem uses Breadth-First Search (BFS) to traverse the tree and calculate the probability of the frog being on the target vertex after t seconds. To implement BFS, the following steps are taken:

  1. Graph Representation: Convert the edge list into an adjacency list (g) using a defaultdict(list). This makes it easier to explore adjacent vertices in the BFS process.

  2. Initialization:

    • A deque named q is used to store tuples that represent the vertex and its current probability. It starts with the root vertex 1 and probability 1.0 since the frog starts at vertex 1.
    • A visited list vis keeps track of which vertices have been visited (to prevent revisiting).

  3. BFS Loop:

    • A while loop is used to process the levels of the tree (in this case, it's also the seconds t).
    • The loop runs until there are no more vertices to visit or the time t runs out.

  4. Processing Each Level:

    • Inside the while loop, a for loop iterates over the vertices in the queue at the current second. It uses the length of the queue to ensure it only processes vertices at the current level.
    • For each vertex u from the front of the queue (using q.popleft()), calculate the count of its unvisited adjacent vertices (cnt). The if u is not the root, we subtract one to avoid counting the parent.
    • If the current vertex u is the target, determine if the frog could still move. If it can't (cnt * t == 0), return the current probability p; else, the frog would leap away, returning 0.

  5. Exploring Neighbors:

    • For each unvisited adjacent vertex v of u, mark it visited (vis[v] = True) and enqueue it with its probability, which is the probability of reaching u (p) divided by the count of unvisited neighbors (cnt). This step equally distributes the probability of jumping to any unvisited neighbor.

  6. Decrement Time:

    • After all vertices at the current second are processed, decrement t.

  7. Termination:

    • If t becomes 0 before we reach the target, or the queue becomes empty (no more vertices to visit), then it's certain the frog is not on the target vertex after t seconds, return 0.

By following this approach, the algorithm ensures that each possible path to the target is considered, and that the probabilities are accurately calculated based on the rules of the frogโ€™s movement. The use of a queue makes it possible to process the tree level by level, which is a fundamental aspect of the BFS algorithm.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose we have the following tree with 5 vertices, where edges = [[1,2],[1,3],[3,4],[3,5]], and we want to calculate the probability that the frog is on vertex 4 after 3 seconds.

Step 0: Before BFS begins

  • Vertex 1 is visited (frog is here at t=0 seconds) with a probability of 1.0.
  • We want to find the probability of the frog being at vertex 4 after t=3 seconds.

Graph Representation

  • Adjacency list g would be {1: [2, 3], 2: [1], 3: [1, 4, 5], 4: [3], 5: [3]}.

Initialization

  1. deque named q: [(1, 1.0)] (vertex, probability)
  2. visited list vis: [False] * 6 (6 including 0-index placeholder)

BFS Loop Starts t = 3 seconds remain

Processing Level t=3

  • From q, vertex 1, the frog has two unvisited vertices to jump to: vertices 2 and 3. The probability is split between them: each gets 1.0 / 2 = 0.5.
  • q after processing: [(2, 0.5), (3, 0.5)]
  • vis: Mark vertex 1 as visited.

Decrement Time: t = 2

Processing Level t=2

  • Vertex 2 is a leaf and has no unvisited neighbors, so we ignore it (the frog can't stay here as it only stops once it has visited all vertices accessible).
  • Vertex 3 has two unvisited adjacent vertices (4 and 5). The probability of the frog jumping to each is 0.5 / 2 = 0.25.
  • q after processing: [(4, 0.25), (5, 0.25)]
  • vis: Mark vertex 3 as visited.

Decrement Time: t = 1

Processing Level t=1

  • Both vertices 4 and 5 are leaf nodes without unvisited neighbors. We check the target vertex.
  • Vertex 4 is our target, and with no unvisited neighbors and t=1, the frog will stay here. We return the probability of 0.25.
  • No need to process vertex 5 as it's not our target.

Termination

  • We have found the probability of the frog being on the target (vertex 4) after 3 seconds to be 0.25.

This example illustrates how we use BFS to calculate the probability of the frog being at a target vertex after a given number of seconds. We have processed the tree level by level, accounting for the rules of the frog's movement and the decrementing time.

Solution Implementation

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
6        # Create a graph using an adjacency list representation
7        graph = defaultdict(list)
8        for u, v in edges:
9            graph[u].append(v)
10            graph[v].append(u)
11      
12        # Queue for BFS with a tuple (node, probability)
13        queue = deque([(1, 1.0)])  
14        # Visited list to keep track of visited nodes
15        visited = [False] * (n + 1)
16        visited[1] = True
17      
18        # Perform BFS for 't' seconds or until queue is empty
19        while queue and t >= 0:
20            # Iterate over all elements in the queue level
21            for _ in range(len(queue)):
22                # Pop the current node and its probability
23                current_node, prob = queue.popleft()
24                # Count of unvisited children nodes
25                unvisited_children_count = len(graph[current_node]) - int(current_node != 1)
26              
27                # If it's the target node, return probability or 0 if there's still time left
28                if current_node == target:
29                    return prob if unvisited_children_count == 0 or t == 0 else 0
30              
31                # Iterate over the connected nodes
32                for neighbor in graph[current_node]:
33                    if not visited[neighbor]:
34                        # Mark as visited and add to queue with updated probability
35                        visited[neighbor] = True
36                        queue.append((neighbor, prob / unvisited_children_count))
37            # Decrement time after each level of BFS
38            t -= 1
39      
40        # If the target is not reached in t seconds, return 0
41        return 0
42
1class Solution {
2    public double frogPosition(int n, int[][] edges, int t, int target) {
3        // Initialize adjacency lists for each node
4        List<Integer>[] graph = new List[n + 1];
5        Arrays.setAll(graph, k -> new ArrayList<>());
6      
7        // Build the undirected graph from edges
8        for (int[] edge : edges) {
9            int from = edge[0], to = edge[1];
10            graph[from].add(to);
11            graph[to].add(from);
12        }
13      
14        // Queue to perform BFS with Pair(Node, Probability)
15        Deque<Pair<Integer, Double>> queue = new ArrayDeque<>();
16        queue.offer(new Pair<>(1, 1.0)); // Start at node 1 with probability 1.0
17      
18        // Visited array to keep track of visited nodes
19        boolean[] visited = new boolean[n + 1];
20        visited[1] = true; // Start node is already visited
21      
22        // Perform BFS up to t steps
23        while (!queue.isEmpty() && t >= 0) {
24            int size = queue.size(); // Number of elements at current time step
25            for (int i = 0; i < size; ++i) {
26                Pair<Integer, Double> current = queue.poll();
27                int currentNode = current.getKey();
28                double probability = current.getValue();
29              
30                // Calculate the number of unvisited children
31                int unvisitedChildrenCount = graph[currentNode].size() - (currentNode == 1 ? 0 : 1);
32              
33                // If target is reached, return probability
34                if (currentNode == target) {
35                    return unvisitedChildrenCount == 0 || t == 0 ? probability : 0;
36                }
37              
38                // Visit all adjacent unvisited nodes
39                for (int neighbor : graph[currentNode]) {
40                    if (!visited[neighbor]) {
41                        visited[neighbor] = true;
42                        queue.offer(new Pair<>(neighbor, probability / unvisitedChildrenCount));
43                    }
44                }
45            }
46            t--; // Decrement time after each level
47        }
48        return 0; // Target not reachable within time t or has more children when t reached 0
49    }
50}
51
1class Solution {
2public:
3    // Calculates the probability that the frog is on the target leaf after t seconds
4    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
5      
6        // Initialize adjacency list for the graph
7        vector<vector<int>> graph(n + 1); 
8        for (const auto& edge : edges) {
9            int from = edge[0], to = edge[1];
10            graph[from].push_back(to);
11            graph[to].push_back(from);
12        }
13      
14        // Initialize a queue to store the node and the probability of reaching that node
15        queue<pair<int, double>> queue;
16        queue.push({1, 1.0}); // Start with the first node and a probability of 1
17      
18        // Create and initialize a visited array to keep track of visited nodes
19        vector<bool> visited(n + 1, false);
20        visited[1] = true; // Mark the first node as visited
21      
22        // BFS traversal of the graph
23        while (!queue.empty() && t >= 0) { // While there are nodes to process and we have time
24            int queueSize = queue.size();
25            while (queueSize-- > 0) { // Process nodes at the current second
26                auto [currentNode, prob] = queue.front();
27                queue.pop();
28              
29                // Calculate the number of unvisited child nodes
30                int unvisitedChildrenCount = 0;
31                for (int neighbor : graph[currentNode]) {
32                    if (!visited[neighbor]) {
33                        unvisitedChildrenCount++;
34                    }
35                }
36              
37                if (currentNode == target) {
38                    // If target is reached and either no more moves are left or no unvisited children
39                    return (unvisitedChildrenCount == 0 || t == 0) ? prob : 0;
40                }
41              
42                // Visit each unvisited neighbor and add to the queue with updated probability
43                for (int neighbor : graph[currentNode]) {
44                    if (!visited[neighbor]) {
45                        visited[neighbor] = true;
46                        queue.push({neighbor, prob / unvisitedChildrenCount});
47                    }
48                }
49            }
50            t--; // Decrement the time after each layer of BFS
51        }
52      
53        // If the frog can't reach the target in t seconds, return 0
54        return 0;
55    }
56};
57
1function frogPosition(numVertices: number, edges: number[][], timeLimit: number, target: number): number {
2    // Graph represented as an adjacency list
3    const graph: number[][] = Array.from({ length: numVertices + 1 }, () => []);
4    for (const [from, to] of edges) {
5        graph[from].push(to);
6        graph[to].push(from);
7    }
8
9    // Queue to perform BFS, starting with vertex 1 and probability 1
10    const queue: number[][] = [[1, 1]];
11  
12    // Visited array to keep track of visited vertices
13    const visited: boolean[] = Array.from({ length: numVertices + 1 }, () => false);
14    visited[1] = true;
15
16    // Loop until the queue is empty or the time limit is reached
17    for (; queue.length > 0 && timeLimit >= 0; --timeLimit) {
18        // Process each level of the BFS tree
19        for (let nodesAtCurrentLevel = queue.length; nodesAtCurrentLevel > 0; --nodesAtCurrentLevel) {
20            const [currentVertex, probability] = queue.shift()!;
21          
22            // Calculate the number of unvisited children
23            const unvisitedChildrenCount = graph[currentVertex].filter(v => !visited[v]).length;
24          
25            // Check if the current vertex is the target
26            if (currentVertex === target) {
27                // If at target, return the probability if time is 0 or if the target is a leaf node
28                return (unvisitedChildrenCount === 0 || timeLimit === 0) ? probability : 0;
29            }
30          
31            // Explore unvisited adjacent vertices
32            for (const adjacentVertex of graph[currentVertex]) {
33                if (!visited[adjacentVertex]) {
34                    visited[adjacentVertex] = true;
35                    queue.push([adjacentVertex, probability / unvisitedChildrenCount]);
36                }
37            }
38        }
39    }
40
41    // Return 0 if the target was not reachable within the time limit
42    return 0;
43}
44
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

The given Python code is intended to solve a frog jumping problem on a tree, represented as an undirected graph. The algorithm aims to calculate the probability that a frog, starting at node 1, will be at a given target node after t seconds.

Time Complexity:

The time complexity of the code can be analyzed as follows:

  • The construction of the graph g takes O(E) time, where E is the number of edges, which in the case of a tree is n - 1. Therefore, this step has a time complexity of O(n).

  • The BFS (Breadth-First Search) is the main part of the algorithm. Each node is visited at most once because the vis array is used to keep track of visited nodes. The BFS loop itself could iterate up to t + 1 times because it decrements t on each outer iteration until t becomes zero.

  • Inside the BFS, for each node, it iterates over all its adjacent nodes. In the worst case, every node would be visited exactly once, and each edge would be considered exactly twice (once for each of its nodes).

  • Therefore, the BFS traversal has a time complexity of O(min(t, n) * (n + E)), which simplifies to O(t * n) because in a tree, the number of edges E is always n - 1.

The overall time complexity is O(t * n).

Space Complexity:

The space complexity of the code can be analyzed as follows:

  • The graph g requires O(n) space, as it contains a list of vertices, and each vertex stores a list of connected nodes.

  • The queue q used for BFS may contain all nodes in the worst case, which requires O(n) space.

  • The vis array is of size n + 1, so it also requires O(n) space.

The overall space complexity is O(n) as the dominating factor, though it can be detailed as O(n) for the graph, O(n) for the BFS queue, and O(n) for the vis array, but when simplified it remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ