Frog Position After T Seconds - Practice Coding Problems

Frog Position After T Seconds - Problem

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.

Input & Output

Example 1 — Basic Tree Navigation

$ Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4

› Output: 0.16666666666666666

💡 Note: Frog starts at 1. At t=1, it chooses between nodes 2,3,7 with probability 1/3 each. If it goes to 2, then at t=2 it chooses between 4,6 with probability 1/2 each. Total probability to reach 4 = (1/3) * (1/2) = 1/6 ≈ 0.1667

Example 2 — Early Arrival Case

$ Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 4, target = 4

› Output: 0.16666666666666666

💡 Note: Frog can reach node 4 at t=2 with probability 1/6. Since node 4 is a leaf (no unvisited neighbors), frog stays there until t=4. Same probability as Example 1.

Example 3 — Impossible Target

$ Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 4

› Output: 0.0

💡 Note: Node 4 requires at least 2 steps to reach from node 1 (1→2→4), but we only have t=1 second. Impossible to reach.

Constraints

1 ≤ n ≤ 100
edges.length == n - 1
edges[i].length == 2
1 ≤ a_i, b_i ≤ n
1 ≤ t ≤ 50
1 ≤ target ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with n=7 vertices, frog starts at vertex 1, target=4, t=2

Path Exploration

Frog randomly chooses among unvisited neighbors at each step

Probability Result

Calculate probability of reaching target at exactly time t

Key Takeaway

🎯 Key Insight: The frog's path is determined by random choices at each node, and probability = product of choice probabilities along the path

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that the frog can only reach the target at exactly time t, or arrive early and stay there if the target is a leaf node. Best approach uses DFS with early termination to explore all possible paths and calculate probabilities. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Early Termination	O(n)	O(n)	Optimized DFS that terminates early when impossible to reach target
DFS Path Exploration	O(n)	O(n)	Explore all possible paths using DFS and calculate probability for each valid path

DFS with Early Termination — Algorithm Steps

Build adjacency list from edges
Use DFS to find path to target
Calculate minimum steps needed to reach target
Handle early arrival case - frog can only stay if no unvisited neighbors
Return probability based on valid paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Path Discovery

DFS finds path to target, checking if reachable in time

Early Arrival Check

If frog arrives early, check if it can stay (leaf node)

Probability Sum

Sum probabilities of all valid arrival scenarios

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double dfs(int** graph, int* graphSize, int node, int parent, int timeLeft, int target, double prob) {
    // Early termination: if target is unreachable in remaining time
    if (timeLeft < 0) {
        return 0.0;
    }
        
    // If we reached target
    if (node == target) {
        // Case 1: Exactly at time t
        if (timeLeft == 0) {
            return prob;
        }
        // Case 2: Arrived early - can only stay if it's a leaf node
        int unvisitedCount = 0;
        for (int i = 0; i < graphSize[node]; i++) {
            if (graph[node][i] != parent) {
                unvisitedCount++;
            }
        }
        if (unvisitedCount == 0) {
            return prob;
        } else {
            return 0.0;  // Must continue moving, can't stay
        }
    }
    
    // If no time left and not at target
    if (timeLeft == 0) {
        return 0.0;
    }
    
    // Get unvisited neighbors (excluding parent)
    int unvisitedNeighbors[1000];
    int unvisitedCount = 0;
    for (int i = 0; i < graphSize[node]; i++) {
        if (graph[node][i] != parent) {
            unvisitedNeighbors[unvisitedCount++] = graph[node][i];
        }
    }
    
    // If no unvisited neighbors, frog stays here forever
    if (unvisitedCount == 0) {
        return 0.0;
    }
    
    // Calculate probability for each neighbor
    double totalProb = 0.0;
    double choiceProb = 1.0 / unvisitedCount;
    
    for (int i = 0; i < unvisitedCount; i++) {
        totalProb += dfs(graph, graphSize, unvisitedNeighbors[i], node, timeLeft - 1, target, prob * choiceProb);
    }
    
    return totalProb;
}

double solution(int n, int** edges, int edgesSize, int t, int target) {
    if (n == 1) {
        return target == 1 ? 1.0 : 0.0;
    }
    
    // Build adjacency list
    int** graph = (int**)malloc((n + 1) * sizeof(int*));
    int* graphSize = (int*)calloc(n + 1, sizeof(int));
    
    for (int i = 0; i <= n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    double result = dfs(graph, graphSize, 1, -1, t, target, 1.0);
    
    // Free memory
    for (int i = 0; i <= n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[1000][2];
    int edgesSize = 0;
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse edges
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            int a, b;
            sscanf(ptr, "[%d,%d]", &a, &b);
            edges[edgesSize][0] = a;
            edges[edgesSize][1] = b;
            edgesSize++;
        }
        ptr++;
    }
    
    int t, target;
    scanf("%d %d", &t, &target);
    
    int** edgePtr = (int**)malloc(edgesSize * sizeof(int*));
    for (int i = 0; i < edgesSize; i++) {
        edgePtr[i] = edges[i];
    }
    
    double result = solution(n, edgePtr, edgesSize, t, target);
    printf("%f\n", result);
    
    free(edgePtr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

DFS visits each node at most once, early termination reduces unnecessary exploration

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n for tree traversal, plus adjacency list storage

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~35 min Avg. Time

445 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler