Frog Position After T Seconds — DSA

Problem#

A frog starts at node 1 of an undirected tree. Each second, it must jump uniformly at random to an unvisited adjacent node. If no unvisited neighbor exists, it stays. Return the probability that it is on target after exactly t seconds.

Examples#

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

Constraints#

1 <= n <= 100, 1 <= t <= 50, 1 <= target <= n.

Hints#

Hint 1

BFS from node 1 tracking the running probability of being at each visited node.

Hint 2

When the frog is at a leaf (no unvisited children) it stays; that’s only valid if the elapsed time has reached t.

Approach#

BFS from root 1. For each node, count its unvisited neighbors. If the frog has reached target: it’s valid if t == 0 OR (t > 0 and target is a leaf with no unvisited children, but only counted at the moment of arrival). Carry probability as a double divided by branch count at each step.

Solution#

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        if (n == 1) return target == 1 ? 1.0 : 0.0;
        vector<vector<int>> g(n + 1);
        for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
        vector<int> seen(n + 1, 0);
        queue<tuple<int,int,double>> q;     // (node, timeUsed, prob)
        q.push({1, 0, 1.0});
        seen[1] = 1;
        while (!q.empty()) {
            auto [u, time, prob] = q.front(); q.pop();
            int unvisited = 0;
            for (int v : g[u]) if (!seen[v]) ++unvisited;
            if (u == target) {
                // Reached target. Valid if time == t, or if frog is stuck here (unvisited == 0) and time <= t.
                if (time == t) return prob;
                if (unvisited == 0) return 0.0;
                return 0.0;
            }
            if (time == t) continue;
            for (int v : g[u]) if (!seen[v]) {
                seen[v] = 1;
                q.push({v, time + 1, prob / unvisited});
            }
        }
        return 0.0;
    }
};

func frogPosition(n int, edges [][]int, t int, target int) float64 {
    if n == 1 {
        if target == 1 {
            return 1.0
        }
        return 0.0
    }
    g := make([][]int, n+1)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    seen := make([]bool, n+1)
    type item struct {
        node, time int
        prob       float64
    }
    q := []item{{1, 0, 1.0}}
    seen[1] = true
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        unvisited := 0
        for _, v := range g[cur.node] {
            if !seen[v] {
                unvisited++
            }
        }
        if cur.node == target {
            if cur.time == t {
                return cur.prob
            }
            return 0.0
        }
        if cur.time == t {
            continue
        }
        for _, v := range g[cur.node] {
            if !seen[v] {
                seen[v] = true
                q = append(q, item{v, cur.time + 1, cur.prob / float64(unvisited)})
            }
        }
    }
    return 0.0
}

from collections import deque
from typing import List

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        if n == 1:
            return 1.0 if target == 1 else 0.0
        g = [[] for _ in range(n + 1)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        seen = [False] * (n + 1)
        seen[1] = True
        q = deque([(1, 0, 1.0)])  # (node, time_used, prob)
        while q:
            node, time, prob = q.popleft()
            unvisited = sum(1 for v in g[node] if not seen[v])
            if node == target:
                if time == t:
                    return prob
                if unvisited == 0:
                    return 0.0
                return 0.0
            if time == t:
                continue
            for v in g[node]:
                if not seen[v]:
                    seen[v] = True
                    q.append((v, time + 1, prob / unvisited))
        return 0.0

function frogPosition(n, edges, t, target) {
    if (n === 1) return target === 1 ? 1.0 : 0.0;
    const g = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
        g[v].push(u);
    }
    const seen = new Array(n + 1).fill(false);
    seen[1] = true;
    const q = [[1, 0, 1.0]]; // [node, timeUsed, prob]
    let head = 0;
    while (head < q.length) {
        const [node, time, prob] = q[head++];
        let unvisited = 0;
        for (const v of g[node]) if (!seen[v]) unvisited++;
        if (node === target) {
            if (time === t) return prob;
            return 0.0;
        }
        if (time === t) continue;
        for (const v of g[node]) {
            if (!seen[v]) {
                seen[v] = true;
                q.push([v, time + 1, prob / unvisited]);
            }
        }
    }
    return 0.0;
}

class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1) return target == 1 ? 1.0 : 0.0;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]);
            g.get(e[1]).add(e[0]);
        }
        boolean[] seen = new boolean[n + 1];
        seen[1] = true;
        Deque<double[]> q = new ArrayDeque<>();
        q.offer(new double[]{1, 0, 1.0});
        while (!q.isEmpty()) {
            double[] cur = q.poll();
            int node = (int) cur[0];
            int time = (int) cur[1];
            double prob = cur[2];
            int unvisited = 0;
            for (int v : g.get(node)) if (!seen[v]) unvisited++;
            if (node == target) {
                if (time == t) return prob;
                if (unvisited == 0) return 0.0;
                return 0.0;
            }
            if (time == t) continue;
            for (int v : g.get(node)) {
                if (!seen[v]) {
                    seen[v] = true;
                    q.offer(new double[]{v, time + 1, prob / unvisited});
                }
            }
        }
        return 0.0;
    }
}

function frogPosition(n: number, edges: number[][], t: number, target: number): number {
    if (n === 1) return target === 1 ? 1.0 : 0.0;
    const g: number[][] = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
        g[v].push(u);
    }
    const seen: boolean[] = new Array(n + 1).fill(false);
    seen[1] = true;
    const q: Array<[number, number, number]> = [[1, 0, 1.0]]; // [node, timeUsed, prob]
    let head = 0;
    while (head < q.length) {
        const [node, time, prob] = q[head++];
        let unvisited = 0;
        for (const v of g[node]) if (!seen[v]) unvisited++;
        if (node === target) {
            if (time === t) return prob;
            if (unvisited === 0) return prob;
            return 0.0;
        }
        if (time === t) continue;
        for (const v of g[node]) {
            if (!seen[v]) {
                seen[v] = true;
                q.push([v, time + 1, prob / unvisited]);
            }
        }
    }
    return 0.0;
}

Editorial#

Trees are loop-free, so once we mark a node visited, the frog can never return. The frog “stops” only at leaves (zero unvisited children); reaching a leaf early means it stays there permanently. We return early at target: if time == t the probability is exact; otherwise the probability is zero unless the frog was forced to stop at target — and in trees if you arrive earlier and have a child, you must move on, hence return 0 in the non-leaf case.

Complexity#

Time: O(n) since each node is enqueued once.
Space: O(n).

Concept revision#

Open the Lock