Collect Coins in a Tree - Practice Coding Problems

Collect Coins in a Tree - 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 2 from 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: If you pass an edge several times, you need to count it into the answer several times.

Input & Output

Example 1 — Simple Tree

$ Input: coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]

› Output: 2

💡 Note: Tree is a straight line. Starting from node 2, we can collect coin at node 0 (distance 2) and coin at node 5 (distance 3 via node 3). We need to visit node 3 and return, so 2 edges total.

Example 2 — Star Configuration

$ Input: coins = [0,0,0,1,1,1], edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]

› Output: 6

💡 Note: Central node 0 connects to all others. Coins are at nodes 3,4,5. From node 0, we can collect all coins at distance 1. We need to visit each coin node and return: 3×2 = 6 edges.

Example 3 — No Coins

$ Input: coins = [0,0,0], edges = [[0,1],[1,2]]

› Output: 0

💡 Note: No coins to collect, so no movement needed.

Constraints

1 ≤ n ≤ 3 × 10⁴
edges.length == n - 1
edges[i].length == 2
0 ≤ ai, bi < n
ai ≠ bi
edges represents a valid tree
coins[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Tree with coins marked at specific nodes

Collection Rule

From any node, collect coins within distance 2

Optimal Path

Find minimum edges for round trip collecting all coins

Key Takeaway

🎯 Key Insight: Since coins can be collected from distance 2, we can prune many unnecessary leaf nodes to find the minimal essential tree structure

Asked in

G Google 45 M Meta 38 A Amazon 32 🍎 Apple 28

Brief HTML summary: The key insight is that we can collect coins from distance ≤ 2, so many leaf nodes can be pruned. Best approach is tree pruning using topological sort to remove unnecessary nodes. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Tree Pruning with Topological Sort	O(n)	O(n)	Remove unnecessary leaf nodes that don't contribute to coin collection
Brute Force - Try All Starting Points	O(n³)	O(n)	Try starting from each node and simulate DFS to collect all coins

Tree Pruning with Topological Sort — Algorithm Steps

Step 1: Build adjacency list and identify coin nodes
Step 2: Remove leaf nodes without coins (2 rounds of pruning)
Step 3: Calculate minimum spanning tree of remaining essential nodes
Step 4: Return 2 × (remaining edges) for round trip

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Tree

Initial tree with coins marked

First Pruning

Remove leaves without coins

Second Pruning

Remove nodes that are distance 2+ from remaining coins

Calculate Cost

2 × remaining edges for round trip

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int degree[MAX_N];
int queue[MAX_N];
int queueFront = 0, queueRear = 0;

void enqueue(int x) {
    queue[queueRear++] = x;
}

int dequeue() {
    return queue[queueFront++];
}

int isEmpty() {
    return queueFront >= queueRear;
}

int solution(int* coins, int coinsSize, int** edges, int edgesSize) {
    int n = coinsSize;
    if (n <= 2) return 0;
    
    // Initialize
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        degree[i] = 0;
    }
    queueFront = queueRear = 0;
    
    // Build graph
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
        degree[a]++;
        degree[b]++;
    }
    
    // First pruning: remove leaves without coins
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1 && coins[i] == 0) {
            enqueue(i);
        }
    }
    
    while (!isEmpty()) {
        int node = dequeue();
        if (degree[node] == 0) continue;
        
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (degree[neighbor] > 0) {
                degree[neighbor]--;
                if (degree[neighbor] == 1 && coins[neighbor] == 0) {
                    enqueue(neighbor);
                }
            }
        }
        degree[node] = 0;
    }
    
    // Second pruning
    queueFront = queueRear = 0;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) {
            enqueue(i);
        }
    }
    
    while (!isEmpty()) {
        int node = dequeue();
        if (degree[node] == 0) continue;
        
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (degree[neighbor] > 0) {
                degree[neighbor]--;
                if (degree[neighbor] == 1) {
                    enqueue(neighbor);
                }
            }
        }
        degree[node] = 0;
    }
    
    // Count remaining edges
    int remainingEdges = 0;
    for (int i = 0; i < edgesSize; i++) {
        if (degree[edges[i][0]] > 0 && degree[edges[i][1]] > 0) {
            remainingEdges++;
        }
    }
    
    return remainingEdges > 0 ? 2 * remainingEdges : 0;
}

int main() {
    char line[10000];
    
    // Read coins
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int coinsArr[MAX_N];
    int coinsSize = 0;
    char* ptr = line + 1; // Skip '['
    char* token = strtok(ptr, ",]");
    while (token) {
        coinsArr[coinsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read edges
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int edgesArr[MAX_N][2];
    int edgesSize = 0;
    if (strcmp(line, "[]") != 0) {
        char* start = strchr(line, '[');
        while (start) {
            start++;
            char* end = strchr(start, ']');
            if (!end) break;
            
            char edgeStr[100];
            strncpy(edgeStr, start, end - start);
            edgeStr[end - start] = '\0';
            
            char* comma = strchr(edgeStr, ',');
            if (comma) {
                *comma = '\0';
                edgesArr[edgesSize][0] = atoi(edgeStr);
                edgesArr[edgesSize][1] = atoi(comma + 1);
                edgesSize++;
            }
            
            start = strchr(end, '[');
        }
    }
    
    int* edges2[edgesSize];
    for (int i = 0; i < edgesSize; i++) {
        edges2[i] = edgesArr[i];
    }
    
    int result = solution(coinsArr, coinsSize, edges2, edgesSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Linear time to build graph, prune nodes, and calculate result - each node processed constant times

✓ Linear Growth

Space Complexity

O(n)

Adjacency list and various tracking arrays each store O(n) elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Tree Pruning with Topological Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler