1377. Frog Position After T Seconds LeetCode Solution

In this guide, you will get 1377. Frog Position After T Seconds LeetCode Solution with the best time and space complexity. The solution to Frog Position After T Seconds problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Frog Position After T Seconds solution in C++
Frog Position After T Seconds solution in Java
Frog Position After T Seconds solution in Python
Additional Resources

1377. Frog Position After T Seconds LeetCode Solution image

Problem Statement of Frog Position After T Seconds

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 <= 100
edges.length == n – 1
edges[i].length == 2
1 <= ai, bi <= n
1 <= t <= 50
1 <= target <= n

Complexity Analysis

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

1377. Frog Position After T Seconds LeetCode Solution in C++

class Solution {
 public:
  double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
    vector<vector<int>> tree(n + 1);
    queue<int> q{{1}};
    vector<bool> seen(n + 1);
    vector<double> prob(n + 1);

    seen[1] = true;
    prob[1] = 1.0;

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      tree[u].push_back(v);
      tree[v].push_back(u);
    }

    while (!q.empty() && t-- > 0)
      for (int sz = q.size(); sz > 0; --sz) {
        const int a = q.front();
        q.pop();
        const int nChildren =
            ranges::count_if(tree[a], [&seen](int b) { return !seen[b]; });
        for (const int b : tree[a]) {
          if (seen[b])
            continue;
          seen[b] = true;
          prob[b] = prob[a] / nChildren;
          q.push(b);
        }
        if (nChildren > 0)
          prob[a] = 0.0;
      }

    return prob[target];
  }
};
/* code provided by PROGIEZ */

1377. Frog Position After T Seconds LeetCode Solution in Java

class Solution {
  public double frogPosition(int n, int[][] edges, int t, int target) {
    List<Integer>[] tree = new List[n + 1];
    Queue<Integer> q = new ArrayDeque<>(List.of(1));
    boolean[] seen = new boolean[n + 1];
    double[] prob = new double[n + 1];

    seen[1] = true;
    prob[1] = 1.0;

    for (int i = 1; i <= n; ++i)
      tree[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      tree[u].add(v);
      tree[v].add(u);
    }

    while (!q.isEmpty() && t-- > 0)
      for (int sz = q.size(); sz > 0; --sz) {
        final int a = q.poll();
        int nChildren = 0;
        for (final int b : tree[a])
          if (!seen[b])
            ++nChildren;
        for (final int b : tree[a]) {
          if (seen[b])
            continue;
          seen[b] = true;
          prob[b] = prob[a] / nChildren;
          q.add(b);
        }
        if (nChildren > 0)
          prob[a] = 0.0;
      }

    return prob[target];
  }
}
// code provided by PROGIEZ

1377. Frog Position After T Seconds LeetCode Solution in Python

class Solution:
  def frogPosition(
      self,
      n: int,
      edges: list[list[int]],
      t: int,
      target: int,
  ) -> float:
    tree = [[] for _ in range(n + 1)]
    q = collections.deque([1])
    seen = [False] * (n + 1)
    prob = [0] * (n + 1)

    prob[1] = 1
    seen[1] = True

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

    for _ in range(t):
      for _ in range(len(q)):
        a = q.popleft()
        nChildren = sum(not seen[b] for b in tree[a])
        for b in tree[a]:
          if seen[b]:
            continue
          seen[b] = True
          prob[b] = prob[a] / nChildren
          q.append(b)
        if nChildren > 0:
          prob[a] = 0

    return prob[target]
 # code by PROGIEZ