Collect Coins in a Tree — Solution in Python, Java & C++
Collect Coins in a Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Collect Coins in a Tree is a hard coding problem on arrays, trees and graph, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Trees, Graph, Topological Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes numbered 0 to n - 1, connected by the n - 1 edges in edges. coins[i] is 1 if node i holds a coin and 0 otherwise.
You start at any node you like. You may repeat these actions any number of times:
- collect every coin at distance at most 2 from your current node, or
- move to an adjacent node.
Return the minimum number of edge traversals needed to collect all the coins and come back to the node you started from. Traversing the same edge twice counts twice.
Example 1
Input: coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: Start at node 2 and collect the coin at node 0; walk to node 3, collect the coin at node 5, and walk back to node 2.
Example 2
Input: coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
Output: 2
Explanation: Start at node 0: collect the coins at 3 and 4, go to node 2, collect the coin at 7, and return to node 0.
Example 3
Input: coins = [1,1,1,1,1,1,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]]
Output: 4
Explanation: Standing on nodes 2 and 4 covers the whole path; walking 2 → 4 and back costs 4.
Constraints
n == coins.length1 <= n <= 3 * 10^40 <= coins[i] <= 1edges.length == n - 1edges[i].length == 20 <= a, b < na != bedges represents a valid tree
Hints for Collect Coins in a Tree
Hint 1
A leaf without a coin is never worth visiting — delete it, and keep deleting until every leaf holds a coin.
Hint 2
Now every leaf has a coin, but a coin can be collected from two steps away: the walk never needs to enter the current leaves, nor the nodes that become leaves once those are gone. Peel off two more layers of leaves.
Hint 3
The walk must cover every edge that is left exactly twice (there and back), so the answer is
2 × remaining edges— or 0 if nothing remains.
How to solve Collect Coins in a Tree
The nodes the walk must visit form a subtree, and a closed walk covering a subtree with k edges costs exactly 2k. That subtree is what is left after trimming useless branches: first every coinless leaf, repeatedly, then two rounds of leaves (because coins are collected from distance 2).
Approach
- Compute degrees;
left = n - 1counts the remaining edges. - Topological trim: queue every leaf with no coin; popping one removes one edge, and a neighbour that becomes a coinless leaf joins the queue.
- Collect the current leaves (all of them hold coins) and remove them, subtracting one edge each.
- Every neighbour whose degree drops to exactly 1 is a second-layer leaf: remove it too, subtracting one more edge.
- Return
max(2 · left, 0).
Why it works
A coinless leaf contributes nothing, so the optimal walk never goes there. After that every leaf has a coin, and that coin is collected from any node within two steps, so the walk can stop two edges short of every leaf; it cannot stop shorter, because then that coin would be three or more steps away. Every edge of the trimmed subtree must be traversed in both directions in a closed walk, giving 2 · edges.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Trimming can consume the whole tree (few coins close together); the edge count then goes negative and the answer is 0.
- In the second phase count a neighbour only when its degree becomes exactly 1, so it is removed once even if several coin leaves hang off it.
- The walk must return to its start, so every remaining edge is paid twice.
Reference solution
Python
from typing import List
def collectTheCoins(coins: List[int], edges: List[List[int]]) -> int:
n = len(coins)
adj = [[] for _ in range(n)]
deg = [0] * n
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
deg[a] += 1
deg[b] += 1
left = n - 1
q = [v for v in range(n) if deg[v] == 1 and coins[v] == 0]
while q:
x = q.pop()
left -= 1
for y in adj[x]:
deg[y] -= 1
if deg[y] == 1 and coins[y] == 0:
q.append(y)
leaves = [v for v in range(n) if deg[v] == 1 and coins[v] == 1]
left -= len(leaves)
for x in leaves:
for y in adj[x]:
deg[y] -= 1
if deg[y] == 1:
left -= 1
return max(2 * left, 0)Java
public static int collectTheCoins(int[] coins, int[][] edges) {
int n = coins.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] deg = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); deg[e[0]]++; deg[e[1]]++; }
int left = n - 1;
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (deg[v] == 1 && coins[v] == 0) q.push(v);
while (!q.isEmpty()) {
int x = q.pop();
left--;
for (int y : adj.get(x)) {
deg[y]--;
if (deg[y] == 1 && coins[y] == 0) q.push(y);
}
}
List<Integer> leaves = new ArrayList<>();
for (int v = 0; v < n; v++) if (deg[v] == 1 && coins[v] == 1) leaves.add(v);
left -= leaves.size();
for (int x : leaves) {
for (int y : adj.get(x)) {
deg[y]--;
if (deg[y] == 1) left--;
}
}
return Math.max(2 * left, 0);
}C++
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
vector<vector<int>> adj(n);
vector<int> deg(n, 0);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); deg[e[0]]++; deg[e[1]]++; }
int left = n - 1;
vector<int> q;
for (int v = 0; v < n; v++) if (deg[v] == 1 && coins[v] == 0) q.push_back(v);
while (!q.empty()) {
int x = q.back();
q.pop_back();
left--;
for (int y : adj[x]) {
deg[y]--;
if (deg[y] == 1 && coins[y] == 0) q.push_back(y);
}
}
vector<int> leaves;
for (int v = 0; v < n; v++) if (deg[v] == 1 && coins[v] == 1) leaves.push_back(v);
left -= leaves.size();
for (int x : leaves) {
for (int y : adj[x]) {
deg[y]--;
if (deg[y] == 1) left--;
}
}
return max(2 * left, 0);
}JavaScript
var collectTheCoins = function(coins, edges) {
var n = coins.length;
var adj = [], deg = [];
for (var i = 0; i < n; i++) { adj.push([]); deg.push(0); }
for (var e = 0; e < edges.length; e++) {
var a = edges[e][0], b = edges[e][1];
adj[a].push(b); adj[b].push(a); deg[a]++; deg[b]++;
}
var left = n - 1, q = [];
for (var v = 0; v < n; v++) if (deg[v] === 1 && coins[v] === 0) q.push(v);
while (q.length > 0) {
var x = q.pop();
left--;
for (var k = 0; k < adj[x].length; k++) {
var y = adj[x][k];
deg[y]--;
if (deg[y] === 1 && coins[y] === 0) q.push(y);
}
}
var leaves = [];
for (var w = 0; w < n; w++) if (deg[w] === 1 && coins[w] === 1) leaves.push(w);
left -= leaves.length;
for (var t = 0; t < leaves.length; t++) {
var lf = leaves[t];
for (var k2 = 0; k2 < adj[lf].length; k2++) {
var z = adj[lf][k2];
deg[z]--;
if (deg[z] === 1) left--;
}
}
return Math.max(2 * left, 0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Trees and Tree Traversals