We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Frog Position After T Seconds

Number: 1493

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an undirected tree with n vertices (1-indexed) and a list of edges, a frog starts at vertex 1 and jumps every second to an unvisited neighbor. When there are multiple unvisited neighbors, the frog chooses one uniformly at random. If there are no unvisited neighbors, the frog will stay in place. Determine the probability that after t seconds the frog ends up on the given target vertex.

Key Insights

  • Represent the tree using an adjacency list.
  • Use depth-first search (DFS) to simulate the frog’s jumps while tracking the elapsed time and cumulative probability.
  • At each vertex, count only the unvisited children to compute the probability for each jump.
  • Special case: If the frog is at the target vertex but can still jump (i.e. it has unvisited children) and there is remaining time, then the probability is 0 unless t seconds have exactly been used or the frog is forced to stay (i.e. no unvisited children).
  • The DFS stops either at t seconds or when no further moves are possible, ensuring correct probability accumulation.

Space and Time Complexity

Time Complexity: O(n) – Each vertex is visited at most once. Space Complexity: O(n) – Storing the adjacency list, visited array, and recursion stack.

Solution

We can solve the problem using a DFS-based approach. We represent the tree as an adjacency list. Starting from vertex 1 with an initial probability of 1, at each recursion level, we traverse to unvisited children while multiplying the current probability by the reciprocal of the number of available children. When the current vertex is the target, we need to check if either we have used exactly t seconds, or if there are no further moves and the elapsed time is less than t (meaning the frog stays). We sum up the probabilities from valid paths. The primary "gotcha" is handling the case where the frog could have moved on but remains at the target because there are no available moves, which is acceptable even if t seconds have not passed.

Code Solutions

# Python solution
def frogPosition(n: int, edges: list, t: int, target: int) -> float:
    from collections import defaultdict
    # Build the adjacency list for the tree
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # DFS helper function to track probability and elapsed time.
    def dfs(node, parent, timeElapsed, probability):
        # If time exactly reached t or no further moves are possible, check for target.
        if timeElapsed == t or (len(graph[node]) == 1 and parent != -1):  
            # If current node is target, return probability.
            return probability if node == target else 0.0
        
        # Count the number of unvisited children.
        countChildren = 0
        for adjacent in graph[node]:
            if adjacent != parent:
                countChildren += 1
        
        # If no unvisited children, frog stays in place.
        if countChildren == 0:
            return probability if node == target else 0.0 
        
        res = 0.0
        # Traverse each unvisited neighbor.
        for adjacent in graph[node]:
            if adjacent != parent:
                res += dfs(adjacent, node, timeElapsed + 1, probability / countChildren)
        return res

    # Special case: if there's only one vertex.
    if n == 1:
        return 1.0 if target == 1 else 0.0

    return dfs(1, -1, 0, 1.0)

# Example usage:
# n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
# Expected output is 0.16666666666666666
print(frogPosition(7, [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], 2, 4))
← Back to All Questions