Collect Coins in a Tree solution and explanation
Cisco
Google
5 more videos on this problem
Collect Coins in a Tree | In Out DP Explained | Weekly Contest 338codingMohan · 1:08:58 · 4K views
Collect Coins in a Tree | Weekly Contest 338 | Leetcode 2603 | OffCampus PhodengeOffCampus Phodenge | Aman Chowdhury · 21:19 · 3K views
2603. Collect Coins in a Tree (Leetcode Hard)Programming Live with Larry · 1:37:40 · 1K views
Leetcode 2603. Collect Coins in a Tree | Topological SortJeezy Leets · 18:57 · 1K views
【每日一题】LeetCode 2603. Collect Coins in a TreeHuifeng Guan · 27:38 · 832 views
Optimizing Coin Collection in an Unrooted Tree: A BFS Solution to LeetCode Hard Problem 2603Talent Navigator · 9:32 · 415 views
The problem
There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given an integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an array coins of size n where coins[i] can be either 0 or 1, where 1 indicates the presence of a coin in the vertex i.
Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times:
- Collect all the coins that are at a distance of at most
2from the current vertex, or - Move to any adjacent vertex in the tree.
Find the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex.
Note that if you pass an edge several times, you need to count it into the answer several times.
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 vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 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 vertex 0, collect the coins at vertices 4 and 3, move to vertex 2, collect the coin at vertex 7, then move back to vertex 0.
Constraints:
n == coins.length1 <= n <= 3 * 1040 <= coins[i] <= 1edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.
Approach overview
Problem Overview: You are given a tree with n nodes where some nodes contain coins. Starting from any node, you can collect coins within distance 2 without visiting every node directly. The goal is to compute the minimum number of edge traversals required to collect all coins and return to the start.
Approach 1: Depth-First Search (DFS) Pruning (O(n) time, O(n) space)
This approach treats the tree as a graph and performs a post-order DFS. Build an adjacency list and recursively process children while tracking whether a subtree contains coins. If a subtree has no coins, its edges can be ignored entirely because visiting it contributes nothing to the final answer. When a subtree contains coins, you add the cost of traversing the edge to that subtree and back (two traversals). The key insight: only edges that lead to coin-containing subtrees matter. DFS propagates coin presence upward so the algorithm prunes unnecessary branches early.
During recursion, maintain a visited set to avoid revisiting parent nodes. Each DFS call returns whether the current subtree has coins and the traversal cost accumulated so far. This approach directly models the idea that useless leaf paths should be removed from the traversal tree.
Approach 2: BFS and Queue-Based Graph Pruning (Topological Sort) (O(n) time, O(n) space)
The optimal approach repeatedly removes useless leaves using a queue. First construct adjacency lists and compute node degrees. Push all leaf nodes without coins into a queue and iteratively remove them. Each removal decreases the degree of its neighbor. This step prunes entire branches that never contribute coins.
After pruning zero-coin leaves, perform two additional rounds of leaf removal. Coins can be collected from nodes within distance two, so the outer two layers of the remaining tree never need to be traversed. Using a queue and degree tracking, remove these layers similar to topological sort. What remains are the edges that must actually be traversed.
The final answer is twice the number of remaining edges because each edge must be walked forward and back. This approach works because tree pruning gradually reveals the minimal subgraph that still contains all coins beyond the free collection radius.
Recommended for interviews: The BFS pruning approach is what most interviewers expect. It shows strong understanding of tree structure, degree tracking, and graph trimming. Starting with the DFS reasoning helps demonstrate intuition about ignoring empty subtrees, but the queue-based pruning solution is cleaner and easier to reason about in O(n).
Approach 1: Depth-First Search (DFS) Approach
This approach uses a DFS traversal to determine the minimal path needed to return to the starting node after collecting all coins. It calculates the number of edges that need to be traversed with consideration of reachable coins at each step. The DFS explores each node and checks its adjacent nodes for coin presence alongside setting an optimal route back.
from collections import defaultdict
def dfs(node, adj, coins, visited):
visited.add(node)
total_coins = coins[node]
for neighbor in adj[node]:
if neighbor not in visited:
total_coins += dfs(neighbor, adj, coins, visited)
return total_coins > 0
def collect_coins(n, edges, coins):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = set()
return max(0, (dfs(0, adj, coins, visited) - 1) * 2)
# Example usage
coins = [1, 0, 0, 0, 0, 1]
edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
print(collect_coins(6, edges, coins))import java.util.*;
public class CoinCollector {
private static List<List<Integer>> adj;
private static boolean[] visited;
private static int[] coins;
private static int dfs(int node) {
visited[node] = true;
int count = coins[node] == 1 ? 1 : 0;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
count += dfs(neighbor);
}
}
return count > 0 ? 1 : 0;
}
public static int collectCoins(int n, int[][] edges, int[] coinsArray) {
adj = new ArrayList<>();
visited = new boolean[n];
coins = coinsArray;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
return (dfs(0) - 1) * 2;
}
public static void main(String[] args) {
int[] coins = {1, 0, 0, 0, 0, 1};
int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}};
System.out.println(collectCoins(6, edges, coins));
}
}#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> coins;
int dfs(int node) {
visited[node] = true;
int count = (coins[node] == 1) ? 1 : 0;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
count += dfs(neighbor);
}
}
return count ? 1 : 0;
}
int collectCoins(int n, vector<vector<int>>& edges, vector<int>& coinsArray) {
adj.assign(n, vector<int>());
visited.assign(n, false);
coins = coinsArray;
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
return (dfs(0) - 1) * 2;
}
int main() {
vector<int> coins = {1, 0, 0, 0, 0, 1};
vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}};
int result = collectCoins(6, edges, coins);
cout << result << endl;
return 0;
}function collectCoins(n, edges, coins) {
const adj = Array.from({ length: n }, () => []);
const visited = new Set();
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
function dfs(node) {
visited.add(node);
let total_coins = coins[node];
for (const neighbor of adj[node]) {
if (!visited.has(neighbor)) {
total_coins += dfs(neighbor);
}
}
return total_coins > 0 ? 1 : 0;
}
return Math.max(0, (dfs(0) - 1) * 2);
}
// Example usage
const coins = [1, 0, 0, 0, 0, 1];
const edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]];
console.log(collectCoins(6, edges, coins));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 30000
typedef struct {
int node;
struct Edge* next;
} Edge;
Edge* adj[MAX_N];
int coins[MAX_N];
bool visited[MAX_N];
void addEdge(int u, int v) {
Edge* newEdge = (Edge*)malloc(sizeof(Edge));
newEdge->node = v;
newEdge->next = adj[u];
adj[u] = newEdge;
}
int dfs(int node) {
visited[node] = true;
int count = coins[node];
for (Edge* e = adj[node]; e; e = e->next) {
if (!visited[e->node]) {
count += dfs(e->node);
}
}
return count;
}
int collectCoins(int n, int edges[][2], int edgesSize, int* coinsArray) {
for (int i = 0; i < n; i++) adj[i] = NULL, visited[i] = false;
for (int i = 0; i < edgesSize; i++) {
int a = edges[i][0], b = edges[i][1];
addEdge(a, b);
addEdge(b, a);
}
for (int i = 0; i < n; i++) coins[i] = coinsArray[i];
return (dfs(0) - 1) * 2;
}
int main() {
int coins[] = { 1, 0, 0, 0, 0, 1 };
int edges[][2] = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5} };
int result = collectCoins(6, edges, 5, coins);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private static List<List<int>> adj;
private static bool[] visited;
private static int[] coins;
private static int dfs(int node) {
visited[node] = true;
int count = coins[node] == 1 ? 1 : 0;
foreach (int neighbor in adj[node]) {
if (!visited[neighbor]) {
count += dfs(neighbor);
}
}
return count > 0 ? 1 : 0;
}
public static int CollectCoins(int n, int[][] edges, int[] coinsArray) {
adj = new List<List<int>>(n);
for (int i = 0; i < n; i++) adj.Add(new List<int>());
visited = new bool[n];
coins = coinsArray;
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
return (dfs(0) - 1) * 2;
}
public static void Main(string[] args) {
int[] coins = {1, 0, 0, 0, 0, 1};
int[][] edges = new int[][] { new int[] {0, 1}, new int[] {1, 2},
new int[] {2, 3}, new int[] {3, 4},
new int[] {4, 5} };
Console.WriteLine(CollectCoins(6, edges, coins));
}
}The Python solution leverages defaultdict for ease of adjacency list generation and makes use of sets for tracking visited nodes. Recursion is employed in the dfs() function to traverse the tree, identifying minimal path conditions for collecting all coins while ensuring duplicates are extricated from travel.
Time Complexity: O(n) by means of visiting all nodes once fully.
Space Complexity: O(n), due to storage for connectivity and node parameters.
Approach 2: BFS and Queue-Based Approach
This approach involves using the Breadth-First Search (BFS) method with a queue to dynamically explore the tree in slices of depth-limited exploration. It records each potential realization of coin acquisition using a range-bound periphery, leveraging spatial layers to evaluate all reachable nodes distinctly within optimal edge traversal focus.
from collections import defaultdict, deque
def bfs(n, start, adj):
visited = [False] * n
level = [0] * n
queue = deque([start])
visited[start] = True
level[start] = 1
while queue:
node = queue.popleft()
for neighbor in adj[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
level[neighbor] = level[node] + 1
return sum(1 for v in visited if v) # Count visited nodes
def collect_coins(n, edges, coins):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
coin_count = sum(coins)
if coin_count == 0:
return 0
return (bfs(n, 0, adj) - 1) * 2
# Example usage
coins = [1, 0, 0, 0, 0, 1]
edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
print(collect_coins(6, edges, coins))import java.util.*;
public class BFSCollectCoins {
private static List<List<Integer>> adj;
private static int[] coins;
private static int bfs(int n, int start) {
boolean[] visited = new boolean[n];
int[] level = new int[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
level[start] = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
level[neighbor] = level[node] + 1;
}
}
}
return queue.size();
}
public static int collectCoins(int n, int[][] edges, int[] coinsArray) {
adj = new ArrayList<>();
coins = coinsArray;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
int coinCount = 0;
for (int coin : coins) coinCount += coin;
if (coinCount == 0) return 0;
return (bfs(n, 0) - 1) * 2;
}
public static void main(String[] args) {
int[] coins = {1, 0, 0, 0, 0, 1};
int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}};
System.out.println(collectCoins(6, edges, coins));
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> adj;
vector<int> coins;
int bfs(int n, int start) {
vector<bool> visited(n, false);
vector<int> level(n, 0);
queue<int> q;
q.push(start);
visited[start] = true;
level[start] = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
level[neighbor] = level[node] + 1;
}
}
}
return q.size();
}
int collectCoins(int n, vector<vector<int>>& edges, vector<int>& coinsArray) {
adj.assign(n, vector<int>());
coins = coinsArray;
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int coinCount = 0;
for (int coin : coins) {
coinCount += coin;
}
if (coinCount == 0) return 0;
return (bfs(n, 0) - 1) * 2;
}
int main() {
vector<int> coins = {1, 0, 0, 0, 0, 1};
vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}};
int result = collectCoins(6, edges, coins);
cout << result << endl;
return 0;
}function bfs(n, start, adj) {
const visited = new Array(n).fill(false);
const level = new Array(n).fill(0);
const queue = [];
queue.push(start);
visited[start] = true;
level[start] = 1;
while (queue.length) {
const node = queue.shift();
for (const neighbor of adj[node]) {
if (!visited[neighbor]) {
queue.push(neighbor);
visited[neighbor] = true;
level[neighbor] = level[node] + 1;
}
}
}
return visited.filter(Boolean).length;
}
function collectCoins(n, edges, coins) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const coinCount = coins.reduce((a, b) => a + b, 0);
if (coinCount === 0) return 0;
return Math.max(0, (bfs(n, 0, adj) - 1) * 2);
}
// Example usage
const coins = [1, 0, 0, 0, 0, 1];
const edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]];
console.log(collectCoins(6, edges, coins));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_N 30000
int adj[MAX_N][MAX_N];
int level[MAX_N];
bool visited[MAX_N];
// BFS helper
int bfs(int n, int start) {
char queue[MAX_N];
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = true;
level[start] = 1;
while (front < rear) {
int node = queue[front++];
for (int i = 0; i < n; i++) {
if (adj[node][i] && !visited[i]) {
queue[rear++] = i;
level[i] = level[node] + 1;
visited[i] = true;
}
}
}
return rear;
}
int collectCoins(int n, int edges[][2], int edgesSize, int* coins) {
memset(adj, 0, sizeof(adj));
memset(level, 0, sizeof(level));
memset(visited, false, sizeof(visited));
for (int i = 0; i < edgesSize; i++) {
adj[edges[i][0]][edges[i][1]] = 1;
adj[edges[i][1]][edges[i][0]] = 1;
}
int coinCount = 0;
for (int i = 0; i < n; i++) {
coinCount += coins[i];
}
if (coinCount == 0) return 0;
return (bfs(n, 0) - 1) * 2;
}
int main() {
int coins[] = {1, 0, 0, 0, 0, 1};
int edges[][2] = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5} };
int result = collectCoins(6, edges, 5, coins);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class BFSCollectCoins {
private static List<List<int>> adj;
private static int[] coins;
private static int bfs(int n, int start) {
bool[] visited = new bool[n];
int[] level = new int[n];
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
visited[start] = true;
level[start] = 1;
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int neighbor in adj[node]) {
if (!visited[neighbor]) {
queue.Enqueue(neighbor);
visited[neighbor] = true;
level[neighbor] = level[node] + 1;
}
}
}
return queue.Count; // Return the count of visited nodes
}
public static int CollectCoins(int n, int[][] edges, int[] coinsArray) {
adj = new List<List<int>>(n);
for (int i = 0; i < n; i++) adj.Add(new List<int>());
coins = coinsArray;
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
int coinCount = 0;
for (int i = 0; i < coinsArray.Length; i++) coinCount += coinsArray[i];
if (coinCount == 0) return 0;
return (bfs(n, 0) - 1) * 2;
}
public static void Main(string[] args) {
int[] coins = {1, 0, 0, 0, 0, 1};
int[][] edges = new int[][] { new int[] {0, 1}, new int[] {1, 2},
new int[] {2, 3}, new int[] {3, 4},
new int[] {4, 5} };
Console.WriteLine(CollectCoins(6, edges, coins));
}
}The Python strategy leverages a deque based breadth-first exploration of graph levels in sequence. The code manipulates default dictionaries to store adjacency configurations and adequately tracks accessible node indices ensuring entire traversal.
Time Complexity: O(n + m), reconciling node count with joint edge contributions.
Space Complexity: O(n + m) grounded with edge tables and visited history corroborations.
Approach 3: Topological sorting
We first convert the edges in edges to the adjacency list g, where g[i] represents all the adjacent nodes of node i, represented by a set.
Then we traverse all nodes and find the nodes where coins[i]=0 and g[i] only has one node (that is, the leaf node where the coin is 0), and add them to the queue q.
Then we continuously remove nodes from the queue and delete them from the adjacent list. Then we check whether the adjacent nodes meet the condition where coins[j]=0 and g[j] only has one node. If it meets, we add it to the queue q. Loop until the queue is empty.
After the above operation, we get a new tree, and the leaf nodes of the tree are all nodes where the coin is 1.
Then, we delete the remaining two layers of leaf nodes, and finally get a tree where all nodes need to be visited. We only need to count the number of edges and multiply it by 2 to get the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes.
Similar problems:
function collectTheCoins(coins: number[], edges: number[][]): number {
const n = coins.length;
const g: Set<number>[] = new Array(n).fill(0).map(() => new Set<number>());
for (const [a, b] of edges) {
g[a].add(b);
g[b].add(a);
}
let q: number[] = [];
for (let i = 0; i < n; ++i) {
if (coins[i] === 0 && g[i].size === 1) {
q.push(i);
}
}
while (q.length) {
const i = q.pop()!;
for (const j of g[i]) {
g[j].delete(i);
if (coins[j] === 0 && g[j].size === 1) {
q.push(j);
}
}
g[i].clear();
}
q = [];
for (let k = 0; k < 2; ++k) {
for (let i = 0; i < n; ++i) {
if (g[i].size === 1) {
q.push(i);
}
}
for (const i of q) {
for (const j of g[i]) {
g[j].delete(i);
}
g[i].clear();
}
}
let ans = 0;
for (const [a, b] of edges) {
if (g[a].size > 0 && g[b].size > 0) {
ans += 2;
}
}
return ans;
}func collectTheCoins(coins []int, edges [][]int) int {
n := len(coins)
g := make([]map[int]bool, n)
for i := range g {
g[i] = map[int]bool{}
}
for _, e := range edges {
a, b := e[0], e[1]
g[a][b] = true
g[b][a] = true
}
q := []int{}
for i, c := range coins {
if c == 0 && len(g[i]) == 1 {
q = append(q, i)
}
}
for len(q) > 0 {
i := q[0]
q = q[1:]
for j := range g[i] {
delete(g[j], i)
if coins[j] == 0 && len(g[j]) == 1 {
q = append(q, j)
}
}
g[i] = map[int]bool{}
}
for k := 0; k < 2; k++ {
q := []int{}
for i := range coins {
if len(g[i]) == 1 {
q = append(q, i)
}
}
for _, i := range q {
for j := range g[i] {
delete(g[j], i)
}
g[i] = map[int]bool{}
}
}
ans := 0
for _, e := range edges {
a, b := e[0], e[1]
if len(g[a]) > 0 && len(g[b]) > 0 {
ans += 2
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(n) by means of visiting all nodes once fully. |
| BFS and Queue-Based Approach | Time Complexity: O(n + m), reconciling node count with joint edge contributions. |
| Topological sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) Pruning | O(n) | O(n) | Useful when reasoning recursively about subtree coin presence and pruning empty branches. |
| BFS Leaf Pruning (Topological Sort) | O(n) | O(n) | Best general solution. Efficiently trims unnecessary leaves and computes minimal traversal edges. |
Frequently asked questions
Is Collect Coins in a Tree easy or hard?
Collect Coins in a Tree is classified as Hard on LeetCode. The difficulty comes from recognizing that the optimal solution involves graph pruning and distance-based reasoning rather than straightforward traversal. Once the pruning insight is clear, the implementation is linear time.
Collect Coins in a Tree Python/Java solution
Python and Java implementations typically build an adjacency list, track node degrees, and use a queue to remove leaves iteratively. After pruning zero-coin leaves and trimming two layers, the remaining edge count determines the answer. The same logic translates easily to C++, C#, and JavaScript.
How to solve Collect Coins in a Tree in O(n)?
Build the tree using adjacency lists and compute node degrees. First remove all leaf nodes with no coins using a queue. Then perform two additional rounds of leaf pruning because nodes within distance two allow coin collection without traversal. Count the remaining edges and multiply by two to get the minimal traversal distance.
What is the best approach for Collect Coins in a Tree?
The BFS leaf-pruning approach using a queue is considered the best solution. It treats the tree as a graph, removes leaf nodes without coins, then trims two additional layers because coins can be collected within distance two. The remaining edges represent the minimum traversal needed. This runs in O(n) time and O(n) space.
Is Collect Coins in a Tree asked at Google/Amazon/Meta?
Tree and graph pruning problems similar to Collect Coins in a Tree appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of graph representation, BFS processing with queues, and pruning strategies often used in topological-style algorithms.
What data structure is used in Collect Coins in a Tree?
The main structures are adjacency lists for representing the tree, a queue for BFS pruning, and arrays for node degrees and coin presence. These structures allow efficient leaf removal and graph updates while maintaining O(n) complexity.
What is the time complexity of Collect Coins in a Tree?
The optimal solutions run in O(n) time where n is the number of nodes. Each node and edge is processed a constant number of times while pruning leaves or traversing the adjacency list. Space complexity is also O(n) due to adjacency lists, degree arrays, and queues.