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

Collect Coins in a Tree

Number: 2717

Difficulty: Hard

Paid? No

Companies: Uber, Lucid

Problem Description

Given an undirected tree with n nodes (numbered 0 to n-1), each node may or may not contain a coin. You can start at any vertex and perform two types of operations any number of times:

  1. From your current vertex, collect all coins within distance ≤ 2.
  2. Move to any adjacent vertex. The goal is to determine the minimum number of edge traversals required to collect all coins and return to your starting vertex.

Key Insights

  • Only parts of the tree that are “relevant” (i.e. can influence coin collection) need to be visited.
  • First, prune all leaves that have no coin. This removes branches that do not contribute to the final answer.
  • Then, because you can collect coins in a radius of 2, perform two additional rounds of removing (even coin‐carrying) leaves. The nodes that remain form the “essential” tree that must be traversed.
  • The answer is simply twice the number of edges in this pruned tree (accounting for going and returning) since in a tree the minimal route is to do a depth-first traversal that “doubles” each edge.
  • If no nodes remain (or if there are no coins to begin with), the minimum cost is zero.

Space and Time Complexity

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

Solution

The solution consists of two main phases. In the first phase, we remove all leaves that do not carry a coin (using a topological sort–like approach), because these parts cannot possibly contribute to collecting any coin. In the second phase, we simulate taking advantage of the “collection radius” by performing two rounds of removal on all current leaves (even those with coins). This effectively “shrinks” the tree down to its core—the set of nodes that you must actually traverse. The final answer is computed as 2×(number of edges in the remaining tree). Note that if nothing remains, then no traversal is needed.

The key data structures used are:

  • An adjacency list (graph) to represent the tree.
  • A degree array to keep track of each node’s number of neighbors.
  • A removed/visited flag array to mark pruned nodes.
  • A queue (or deque) is used for the pruning process.

After pruning, the remaining tree (if not empty) has “required” edges. Since each edge must be traversed twice (forth and back), the answer is 2 * (# edges remaining).

Code Solutions

from collections import defaultdict, deque

def collectCoinsInTree(coins, edges):
    n = len(coins)
    # If there are no coins at all, no traversal is needed.
    if sum(coins) == 0:
        return 0

    # Build the tree as an adjacency list and record degrees.
    graph = defaultdict(list)
    degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1

    removed = [False] * n
    dq = deque()
    # Phase 1: Remove all leaves that do not have a coin.
    for i in range(n):
        if degree[i] == 1 and coins[i] == 0:
            dq.append(i)
            removed[i] = True

    while dq:
        node = dq.popleft()
        for nei in graph[node]:
            if not removed[nei]:
                degree[nei] -= 1
                if degree[nei] == 1 and coins[nei] == 0:
                    removed[nei] = True
                    dq.append(nei)

    # Phase 2: Remove leaves in two rounds to take advantage of the collectible radius.
    for _ in range(2):
        dq = deque()
        for i in range(n):
            if not removed[i] and degree[i] == 1:
                dq.append(i)
        while dq:
            node = dq.popleft()
            if removed[node]:
                continue
            removed[node] = True
            for nei in graph[node]:
                if not removed[nei]:
                    degree[nei] -= 1

    # Count remaining nodes and remaining edges.
    remaining_nodes = [i for i in range(n) if not removed[i]]
    if not remaining_nodes:
        return 0

    remaining_edges = 0
    for i in range(n):
        if not removed[i]:
            # Count each edge once.
            for j in graph[i]:
                if not removed[j] and j > i:
                    remaining_edges += 1

    # The answer is 2 * (number of remaining edges).
    return 2 * remaining_edges

# Example usage:
coins = [1, 0, 0, 0, 0, 1]
edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
print(collectCoinsInTree(coins, edges))  # Expected output: 2
← Back to All Questions