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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Collect Coins in a Tree

Difficulty: Hard

Problem Description

You are given an undirected and unrooted tree with n nodes and edges that connect them. Each node may contain a coin. Starting at any node, your goal is to collect all coins in the tree while minimizing the number of edges traversed to return to the starting point. You can collect coins from nodes that are at a distance of at most 2 from your current position.

Key Insights

  • The tree structure means there are no cycles, making traversal straightforward.
  • You only need to consider nodes with coins, as other nodes do not contribute to the total distance needed.
  • Using a depth-first search (DFS) or breadth-first search (BFS) can effectively explore the tree.
  • You can collect coins from nodes at a distance of 2, which reduces the number of traversals needed.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, as each node and edge is processed once. Space Complexity: O(n), for the adjacency list representation of the tree and the recursion stack in DFS.

Solution

To solve the problem, we can perform a depth-first search (DFS) starting from any node. During the DFS, we will keep track of whether we need to collect coins from child nodes. If any child node contains coins, we will count the edges required to travel to that node and back. The algorithm will:

  1. Build an adjacency list from the given edges.
  2. Use DFS to explore each node, checking if it or any of its descendants contain coins.
  3. Accumulate the distance traveled based on the need to collect coins from child nodes and return to the starting point.

Code Solutions

def collectCoins(coins, edges):
    from collections import defaultdict

    # Build the adjacency list
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    def dfs(node, parent):
        total_distance = 0
        has_coin = coins[node]

        for neighbor in graph[node]:
            if neighbor != parent:
                distance, child_has_coin = dfs(neighbor, node)
                if child_has_coin:
                    total_distance += distance + 2  # go to neighbor and back
                has_coin |= child_has_coin

        return total_distance, has_coin

    total_distance, _ = dfs(0, -1)
    return total_distance
← Back to All Questions