Collect Coins in a Tree

Hard
1707.

Collect Coins in a Tree

Collect Coins in a Tree is a hard coding problem on arrays, trees and graph, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 3 * 10^4
  • 0 <= coins[i] <= 1
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a, b < n
  • a != b
  • edges represents a valid tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} coins
 * @param {number[][]} edges
 * @return {number}
 */
var collectTheCoins = function(coins, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= n <= 3 * 10^4
  • 0 <= coins[i] <= 1
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a, b < n
  • a != b
  • edges represents a valid tree

Hints for Collect Coins in a Tree

  1. Hint 1

    A leaf without a coin is never worth visiting — delete it, and keep deleting until every leaf holds a coin.

  2. 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.

  3. 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

  1. Compute degrees; left = n - 1 counts the remaining edges.
  2. Topological trim: queue every leaf with no coin; popping one removes one edge, and a neighbour that becomes a coinless leaf joins the queue.
  3. Collect the current leaves (all of them hold coins) and remove them, subtracting one edge each.
  4. Every neighbour whose degree drops to exactly 1 is a second-layer leaf: remove it too, subtracting one more edge.
  5. 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