LeetCode 1377: Frog Position After T Seconds Solution

Master LeetCode problem 1377 (Frog Position After T Seconds), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1377. Frog Position After T Seconds

Hard

Tree Depth-First Search Breadth-First Search Graph

Problem Explanation

Explanation:

We can solve this problem using DFS on the tree.
At each vertex, we calculate the probability of reaching that vertex after t seconds.
If the frog reaches the target vertex in exactly t seconds, we return the probability of being at the target vertex.
If the frog reaches the target vertex before t seconds and then stays there, we return the probability of being at the target vertex at t seconds.
If the frog never reaches the target vertex within t seconds, we return 0.

Time Complexity: O(n)
Space Complexity: O(n)

Solution Code

class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        return dfs(graph, 1, t, target, new boolean[n + 1]);
    }
    
    private double dfs(List<List<Integer>> graph, int node, int t, int target, boolean[] visited) {
        if (t == 0) {
            return node == target ? 1.0 : 0.0;
        }
        
        visited[node] = true;
        double probability = 0.0;
        int neighbors = 0;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                neighbors++;
            }
        }
        
        if (neighbors == 0) {
            return node == target ? 1.0 : 0.0;
        }
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                probability += dfs(graph, neighbor, t - 1, target, visited) / neighbors;
            }
        }
        
        return probability;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1377 (Frog Position After T Seconds)?

This page provides optimized solutions for LeetCode problem 1377 (Frog Position After T Seconds) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1377 (Frog Position After T Seconds)?

The time complexity for LeetCode 1377 (Frog Position After T Seconds) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1377 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1377 in Java, C++, or Python.

Back to LeetCode Solutions