LeetCode 2603 - Collect Coins in a Tree
The problem is about collecting coins located on the nodes of a tree with the minimum number of edge traversals. We are given a tree with n nodes, represented by an edge list, and an array coins indicating whether a coin is present at each node.
Difficulty: 🔴 Hard
Topics: Array, Tree, Graph Theory, Topological Sort
Solution
Problem Understanding
The problem is about collecting coins located on the nodes of a tree with the minimum number of edge traversals. We are given a tree with n nodes, represented by an edge list, and an array coins indicating whether a coin is present at each node. We are allowed two operations: collect all coins within distance 2 from the current node or move to an adjacent node. The goal is to determine the minimum total number of edges we need to traverse to collect all coins and return to the starting node.
The input consists of a coins array of size n and an edges array of size n-1. The constraints indicate that n can be up to 3 * 10^4, which rules out brute-force approaches that explore all paths, because they would be too slow. The input is guaranteed to form a valid tree, which means there are no cycles and the graph is connected.
Important edge cases include trees where all coins are at the leaves, trees with no coins, and trees where coins are clustered near the center. These could affect how many edges are actually necessary to traverse.
Approaches
A brute-force approach would try starting at every node and simulate collecting coins by performing a BFS or DFS traversal while keeping track of distance for collection. While this would produce the correct result, it is inefficient. Considering each node as a starting point and simulating all possible moves results in exponential time complexity due to the combinatorial nature of the paths. With n up to 3 * 10^4, this is infeasible.
The key insight for an optimal solution is that we only need to keep edges that are "necessary" to reach coins. Any leaf nodes or edges that do not lead to coins within two steps can be removed. Using a process similar to "pruning leaves" or a two-pass topological sort on the tree allows us to reduce the tree to only the essential edges. After pruning, the remaining edges represent the minimal path that must be traversed twice (there and back), except for edges close enough to start nodes that allow collection within distance 2.
The steps are: prune leaves without coins, prune leaves two times to account for the distance-2 collection rule, and then calculate the total remaining edges multiplied by 2.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) or worse | O(n) | Simulate collecting coins from every start node, infeasible for large n |
| Optimal | O(n) | O(n) | Prune unnecessary leaves and compute remaining edges |
Algorithm Walkthrough
- Build an adjacency list from the edge list for the tree representation. This allows efficient traversal of neighbors.
- Initialize a degree array to track the number of neighbors for each node.
- Identify all leaf nodes (nodes with degree 1) and put them in a queue. Leaves are candidate nodes for pruning if they do not contain coins.
- Perform a BFS-like pruning of leaves: for each leaf, if it does not contain a coin, remove it from the tree, decrease the degree of its neighbor, and if the neighbor becomes a leaf, enqueue it. Repeat until no leaves can be removed.
- After pruning leaves without coins, perform a second pruning pass for distance-2 collection: remove all current leaves, then remove new leaves created by the first removal. This accounts for collecting coins within two steps without traversing extra edges.
- Count the remaining edges in the tree. Each remaining edge needs to be traversed twice (going and returning).
- Return the total number of traversals as the answer.
Why it works: By pruning leaves without coins and applying distance-2 logic, we are left only with edges that are necessary to collect coins. Every traversal outside of this pruned subtree is redundant, so counting the remaining edges twice gives the minimum number of moves.
Python Solution
from collections import deque
from typing import List
class Solution:
def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
n = len(coins)
if n == 1:
return 0
adj = [[] for _ in range(n)]
degree = [0] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
degree[u] += 1
degree[v] += 1
leaves = deque()
for i in range(n):
if degree[i] == 1:
leaves.append(i)
removed = [False] * n
# First prune leaves without coins
for _ in range(n):
new_leaves = deque()
while leaves:
leaf = leaves.popleft()
if coins[leaf]:
continue
removed[leaf] = True
for neighbor in adj[leaf]:
if removed[neighbor]:
continue
degree[neighbor] -= 1
if degree[neighbor] == 1:
new_leaves.append(neighbor)
if not new_leaves:
break
leaves = new_leaves
# Second prune leaves for distance-2 collection
leaves = deque([i for i in range(n) if degree[i] == 1 and not removed[i]])
for _ in range(2):
new_leaves = deque()
while leaves:
leaf = leaves.popleft()
removed[leaf] = True
for neighbor in adj[leaf]:
if removed[neighbor]:
continue
degree[neighbor] -= 1
if degree[neighbor] == 1:
new_leaves.append(neighbor)
leaves = new_leaves
remaining_edges = sum(degree[i] for i in range(n) if not removed[i]) // 2
return remaining_edges * 2
Explanation: We build an adjacency list and degree array to efficiently track leaf nodes. We perform two pruning phases: the first removes leaves with no coins, the second accounts for distance-2 collection. Remaining edges are counted and doubled for round trips.
Go Solution
package main
func collectTheCoins(coins []int, edges [][]int) int {
n := len(coins)
if n == 1 {
return 0
}
adj := make([][]int, n)
degree := make([]int, n)
for _, e := range edges {
u, v := e[0], e[1]
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
degree[u]++
degree[v]++
}
removed := make([]bool, n)
leaves := []int{}
for i := 0; i < n; i++ {
if degree[i] == 1 {
leaves = append(leaves, i)
}
}
// First pruning
for len(leaves) > 0 {
newLeaves := []int{}
for _, leaf := range leaves {
if coins[leaf] == 1 {
continue
}
removed[leaf] = true
for _, neighbor := range adj[leaf] {
if removed[neighbor] {
continue
}
degree[neighbor]--
if degree[neighbor] == 1 {
newLeaves = append(newLeaves, neighbor)
}
}
}
leaves = newLeaves
}
// Second pruning for distance-2
leaves = []int{}
for i := 0; i < n; i++ {
if degree[i] == 1 && !removed[i] {
leaves = append(leaves, i)
}
}
for i := 0; i < 2; i++ {
newLeaves := []int{}
for _, leaf := range leaves {
removed[leaf] = true
for _, neighbor := range adj[leaf] {
if removed[neighbor] {
continue
}
degree[neighbor]--
if degree[neighbor] == 1 {
newLeaves = append(newLeaves, neighbor)
}
}
}
leaves = newLeaves
}
remainingEdges := 0
for i := 0; i < n; i++ {
if !removed[i] {
remainingEdges += degree[i]
}
}
return remainingEdges
}
Go-specific notes: Go does not allow dynamic array slicing in the same way Python does for dequeues, so we use slices and append for queues. Boolean array and integer slices work similarly. Edge counting is done with integer division since each edge is counted twice in the adjacency list.
Worked Examples
Example 1:
coins = [1,0,0,0,0,1]
edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
Initial leaf nodes: [0,5]
First pruning: leaf 0 has coin, leaf 5 has coin, no removal
Distance-2 pruning: remove leaves at ends to account for 2-step collection → edges [1,2,3,4] remain
Remaining edges: 1-2,2-3,3-4 → 4 edges, multiply by 2 → total 2 moves since distance-2 collection reduces traversal
Example 2:
coins = [0,0,0,1,1,0,0,1]
edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
Initial leaf nodes: [