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:
- You may start at any vertex.
- From the current vertex, you may collect all coins within a distance of 2 edges, inclusive.
- 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:
-
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 placeb
ina
's adjacency set and vice versa. -
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
andcoins[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 neighborj
. - 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.
- A queue
-
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.
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 to1
and2
.1
is connected to0
,3
, and4
.2
only connects to0
.3
and4
only connect to1
.- Vertices
1
and2
have coins while0
,3
, and4
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 to0
and4
. - 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.
Which of the following is a good use case for backtracking?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed