2603. Collect Coins in a Tree


Problem Description

In this problem, we are given a tree which is an undirected and unrooted graph without any cycles. The tree consists of n vertices indexed from 0 to n-1, and we have n-1 edges that connect the vertices, forming the edges of this tree. The edges are represented by a 2D integer array where each subarray consists of 2 integers indicating that there is an edge connecting those two vertices.

Additionally, we have an array coins of size n, where each entry is either 0 or 1. A 1 at index i means that there is a coin present at vertex i in the tree. The goal of the problem is to find and collect all these coins in an optimized manner. The rules for collecting coins are:

  1. You may start at any vertex.
  2. From the current vertex, you may collect all coins within a distance of 2 edges, inclusive.
  3. You also have the option to move to any adjacent vertex of the current one.

The objective is to determine the minimum number of edge traversals required to collect all the coins and return to the starting vertex. Moreover, each time an edge is passed, it counts towards the total edge traversal count.

Intuition

To approach this problem, we think about pruning the tree to simplify our task. If we remove vertices that don't have coins and don't lead to vertices with coins, we simplify the tree by reducing the number of edges we need to worry about.

The primary intuition around the solution is derived from topological sorting. By treating leaves of the tree (vertices with a single connection or edge) which don't have a coin as unnecessary, we can iteratively prune the tree. When a vertex has only one other vertex it is connected to and does not have a coin on it, it's essentially not worth visiting in the coin collection process. Therefore such a vertex, along with the edge connecting it, can be removed from consideration.

By doing this iteratively from leaf nodes inwards, we remove all such "unnecessary" nodes until we are left with a subtree where all leaf nodes contain coins. Effectively, we are simplifying the tree to a version where only vertices with coins (or leading to vertices with coins within two edges) remain.

After pruning all zero-coin leaves, we do one final step of pruning two layers of leaves. The reason is that, for any leaf node after the initial pruning, since it must have a coin, we would already collect its coin when visiting its parent node (as it's within the reach of 2 edges). Thus, we only consider edges that lead to "non-leaf" vertices in our final tree.

Finally, as we need to both collect coins and return to the starting vertex, we need to traverse each of the remaining edges twice - going towards the coin-bearing vertices and coming back. This is why we multiply the final edge count by 2 to get the minimum number of moves required to collect all coins and return to the starting position.

Learn more about Tree, Graph and Topological Sort patterns.

Solution Approach

The solution to the problem leverages graph traversal and uses the concept of pruning a tree by removing unnecessary leaves — vertices that don't contribute to the collection of coins. The approach follows these steps:

  1. Convert Edges to Adjacency List: We start by converting the edge list representation of the tree into an adjacency list for easier manipulation of graph nodes. For each edge (a, b), we place b in a's adjacency set and vice versa.

  2. Initial Pruning: Next, we identify all the leaf nodes where coins are absent by checking each vertex. A leaf node is identified where len(g[i]) == 1 and coins[i] == 0, meaning it only has one adjacent vertex and no coin on it. We then proceed to prune these leaves iteratively:

    • A queue q initialized with all such identified leaves.
    • We remove each vertex i from the queue and detach it from the tree by removing it from the adjacency list of its neighbor j.
    • If the neighbor j becomes a leaf after removal and also doesn't have a coin, it is added to the queue. This pruning continues until no more leaf vertices can be pruned.
  3. Leaf Reduction: A further reduction process involves trimming down two layers of leaves. This is crucial because in terms of moves:

    • The second to last layer of leaves doesn't require a direct visit as coins can be collected by visiting their parent nodes.
    • The last layer of leaves will be visited once in the traversal to collect the coins.
  4. Count Remaining Edges: After final pruning, we count the remaining edges. These are the critical edges that must be traversed twice (once for going to the coin and once for returning). We iterate through the edges and check if both vertices connected by the edge are still in the graph (len(g[a]) > 0 and len(g[b]) > 0). The edges that meet this criterion reflect the necessary traversal path for coin collection.

The final step in the calculation is to multiply the count of these edges by two, giving us the overall minimum number of moves necessary to collect all the coins and return to the start point.

This solution is efficient since it systematically reduces the size of the problem by eliminating vertices and edges that don't contribute to the solution, thus making it easier to count the minimum traversal needed for the remaining critical edges.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Example Walkthrough

Let's consider a tree with n = 5 vertices, which has the following edge configuration and coin distribution:

Edges: [[0, 1], [0, 2], [1, 3], [1, 4]] Coins: [0, 1, 1, 0, 0]

In this example:

  • 0 is connected to 1 and 2.
  • 1 is connected to 0, 3, and 4.
  • 2 only connects to 0.
  • 3 and 4 only connect to 1.
  • Vertices 1 and 2 have coins while 0, 3, and 4 do not.

Step 1: Convert Edges to Adjacency List

We create an adjacency list representation of the graph as follows:

1g = {
2    0: {1, 2},
3    1: {0, 3, 4},
4    2: {0},
5    3: {1},
6    4: {1}
7}

Step 2: Initial Pruning

We identify leaf nodes without coins: vertices 3 and 4. We put them in a queue and start pruning:

  • Remove 3, which is a leaf and doesn't have a coin. 1 remains connected to 0 and 4.
  • Then vertex 4 satisfies the leaf condition and is also pruned.

After pruning, our adjacency list updates to:

1g = {
2    0: {1, 2},
3    1: {0},
4    2: {0}
5}

Vertices 3 and 4 have been pruned off because they didn't have coins and were leaves.

Step 3: Leaf Reduction

Next, we observe that vertices 1 and 2 have become leaves. However, we only prune 1 because although both are leaves, 2 has a coin making it critical to the collection process:

Our adjacency list updates to:

1g = {
2    0: {2},
3    2: {0}
4}

Only vertices 0 and 2 remain with a single critical edge connecting them.

Step 4: Count Remaining Edges

There is only one edge left in the graph connecting 0 and 2. Since we need to collect coins and return to the starting vertex by traversing each edge twice:

Number of remaining edges * 2 = 1 * 2 = 2

Thus, the minimum number of moves required to collect all the coins and return to the starting point is 2.

Through this walk-through, it is clear how pruning unnecessary leaf vertices and reducing the tree to a critical traversal path simplifies the graph to efficiently count the minimum number of edge traversals without visiting non-coin-bearing vertices.

Solution Implementation

1from collections import defaultdict, deque
2
3class Solution:
4    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
5        # Create a graph represented as an adjacency list
6        graph = defaultdict(set)
7        for start, end in edges:
8            graph[start].add(end)
9            graph[end].add(start)
10      
11        num_nodes = len(coins)
12      
13        # Queue for BFS, initialized with leaf nodes having 0 coins
14        queue = deque([node for node in range(num_nodes) if len(graph[node]) == 1 and coins[node] == 0])
15      
16        # Process nodes with BFS approach
17        while queue:
18            current = queue.popleft()
19            for neighbor in graph[current]:
20                graph[neighbor].remove(current)  # Remove the edge to the current node
21                if coins[neighbor] == 0 and len(graph[neighbor]) == 1:
22                    queue.append(neighbor)  # Add leaf neighbors with 0 coins to the queue
23            graph[current].clear()  # Clear the edges of the current node
24     
25        # Repeat the edge-clearing process twice
26        for _ in range(2):
27            # Find all nodes with exactly one connection
28            single_connection_nodes = [node for node in range(num_nodes) if len(graph[node]) == 1]
29            for node in single_connection_nodes:
30                for neighbor in graph[node]:
31                    graph[neighbor].remove(node)  # Remove the edge
32                graph[node].clear()  # Clear the edges of the node
33      
34        # Count the remaining edges after clearing, and multiply by 2 since each edge is counted twice
35        remaining_edges_count = sum(len(graph[a]) > 0 and len(graph[b]) > 0 for a, b in edges) * 2
36      
37        return remaining_edges_count
38
1class Solution {
2    public int collectTheCoins(int[] coins, int[][] edges) {
3        // Get the number of nodes which is the length of the coins array
4        int nodeCount = coins.length;
5      
6        // Create an array of hash sets to represent the adjacency list of the graph
7        Set<Integer>[] graph = new Set[nodeCount];
8        Arrays.setAll(graph, x -> new HashSet<>());
9      
10        // Build the graph from the edges
11        for (var edge : edges) {
12            int from = edge[0], to = edge[1];
13            graph[from].add(to);
14            graph[to].add(from);
15        }
16      
17        // Create a queue to process nodes
18        Deque<Integer> queue = new ArrayDeque<>();
19      
20        // Enqueue leaf nodes with a coin value of 0
21        for (int i = 0; i < nodeCount; ++i) {
22            if (coins[i] == 0 && graph[i].size() == 1) {
23                queue.offer(i);
24            }
25        }
26      
27        // Perform a BFS to remove leaf nodes with 0 coins
28        while (!queue.isEmpty()) {
29            int node = queue.poll();
30            for (int neighbor : graph[node]) {
31                graph[neighbor].remove(node);
32                if (coins[neighbor] == 0 && graph[neighbor].size() == 1) {
33                    queue.offer(neighbor);
34                }
35            }
36            graph[node].clear();
37        }
38      
39        // Reset queue for next round of processing
40        queue.clear();
41      
42        // Process the graph twice to remove remaining leaf nodes
43        for (int k = 0; k < 2; ++k) {
44            for (int i = 0; i < nodeCount; ++i) {
45                if (graph[i].size() == 1) {
46                    queue.offer(i);
47                }
48            }
49            while (!queue.isEmpty()) {
50                int leafNode = queue.poll();
51                for (int neighbor : graph[leafNode]) {
52                    graph[neighbor].remove(leafNode);
53                }
54                graph[leafNode].clear();
55            }
56        }
57      
58        // Calculate the result based on the remaining graph structure
59        int result = 0;
60        for (var edge : edges) {
61            int from = edge[0], to = edge[1];
62            if (graph[from].size() > 0 && graph[to].size() > 0) {
63                result += 2;
64            }
65        }
66      
67        // Return the total coins that can be collected
68        return result;
69    }
70}
71
1class Solution {
2public:
3    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
4        int numCoins = coins.size();
5
6        // Create an adjacency set for each node to represent the graph
7        unordered_set<int> graph[numCoins];
8        for (auto& edge : edges) {
9            int nodeA = edge[0], nodeB = edge[1];
10            graph[nodeA].insert(nodeB);
11            graph[nodeB].insert(nodeA);
12        }
13
14        // Initialize a queue to perform a BFS-like operation
15        queue<int> bfsQueue;
16
17        // Add leaf nodes with 0 coins to the queue
18        for (int i = 0; i < numCoins; ++i) {
19            if (coins[i] == 0 && graph[i].size() == 1) {
20                bfsQueue.push(i);
21            }
22        }
23
24        // Process nodes with 0 coins and remove them from graph
25        while (!bfsQueue.empty()) {
26            int currentNode = bfsQueue.front();
27            bfsQueue.pop();
28
29            for (int neighbor : graph[currentNode]) {
30                graph[neighbor].erase(currentNode); // Remove the edge
31                if (coins[neighbor] == 0 && graph[neighbor].size() == 1) {
32                    bfsQueue.push(neighbor); // Add the leaf nodes with 0 coins
33                }
34            }
35            graph[currentNode].clear();
36        }
37
38        // Remove leaf nodes from the graph twice
39        for (int iteration = 0; iteration < 2; ++iteration) {
40            vector<int> leafNodes;
41            for (int i = 0; i < numCoins; ++i) {
42                if (graph[i].size() == 1) {
43                    leafNodes.push_back(i);
44                }
45            }
46            // Detach leaf nodes from their neighbors
47            for (int leafNode : leafNodes) {
48                for (int neighbor : graph[leafNode]) {
49                    graph[neighbor].erase(leafNode);
50                }
51                graph[leafNode].clear();
52            }
53        }
54
55        // Calculate the result from the remaining edges in the graph
56        int result = 0;
57        for (auto& edge : edges) {
58            int nodeA = edge[0], nodeB = edge[1];
59            if (graph[nodeA].size() && graph[nodeB].size()) {
60                result += 2; // Each remaining edge contributes 2 to the answer
61            }
62        }
63
64        return result;
65    }
66};
67
1function collectTheCoins(coins: number[], edges: number[][]): number {
2    // Initialize the number of vertices based on the length of the coins array.
3    const numVertices = coins.length;
4
5    // Create an adjacency list representation of the graph.
6    const graph: Set<number>[] = new Array(numVertices).fill(0).map(() => new Set<number>());
7
8    // Fill the adjacency list with edges from the input.
9    for (const [vertex1, vertex2] of edges) {
10        graph[vertex1].add(vertex2);
11        graph[vertex2].add(vertex1);
12    }
13
14    // Initialize an empty queue for processing leaf nodes.
15    let queue: number[] = [];
16  
17    // Enqueue vertices which are leaf nodes and have a coin count of 0.
18    for (let i = 0; i < numVertices; ++i) {
19        if (coins[i] === 0 && graph[i].size === 1) {
20            queue.push(i);
21        }
22    }
23
24    // Process the queue until empty, remove leaf nodes.
25    while (queue.length) {
26        const currentNode = queue.pop()!;
27
28        // Remove the edge between the current node and its neighbor.
29        for (const neighbor of graph[currentNode]) {
30            graph[neighbor].delete(currentNode);
31          
32            // If the neighbor becomes a leaf node and has no coin, add to queue.
33            if (coins[neighbor] === 0 && graph[neighbor].size === 1) {
34                queue.push(neighbor);
35            }
36        }
37
38        // Clear all edges from the processed node.
39        graph[currentNode].clear();
40    }
41
42    // Reset the queue for a second pass.
43    queue = [];
44
45    // Perform two sweeps for identifying leaf nodes.
46    for (let sweep = 0; sweep < 2; ++sweep) {
47        // Enqueue any leaf nodes.
48        for (let i = 0; i < numVertices; ++i) {
49            if (graph[i].size === 1) {
50                queue.push(i);
51            }
52        }
53
54        // Remove all queued leaf nodes from the graph.
55        for (const leafNode of queue) {
56            for (const neighbor of graph[leafNode]) {
57                graph[neighbor].delete(leafNode);
58            }
59            graph[leafNode].clear();
60        }
61    }
62
63    // Now count the remaining edges.
64    let totalEdges = 0;
65    for (const [vertex1, vertex2] of edges) {
66        if (graph[vertex1].size > 0 && graph[vertex2].size > 0) {
67            totalEdges += 2;
68        }
69    }
70
71    // Return the total number of remaining edges.
72    return totalEdges;
73}
74

Time and Space Complexity

The time complexity of the provided function collectTheCoins is O(n), where n is the number of nodes (or vertices) in the graph. This is because the function processes each node and edge a constant number of times. The first while loop iterates over each node with one neighbor and a coin value of 0, popping from the deque and updating the graph at most once for each node. The nested for loop inside this while loop runs at most once per edge, since once a node is processed, it is removed. The subsequent loops run a fixed two times and iteratively process leaf nodes of the current graph, which is again proportional to the number of nodes in the graph.

Now let's assess the space complexity. The space complexity is also O(n), primarily dictated by the storage of the graph g, which is stored in a defaultdict of sets, along with the deque q which, at its maximum, might hold all the nodes if they initially have only one edge and 0 as their coin count (although this situation will rapidly deplete as the algorithm progresses). As these data structures store information related to each node and edge at most once, the space used is linearly proportional to the size of the input graph, which has n nodes and can have at most O(n) edges in a simple graph scenario.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄