Collect Coins in a Tree

Hard Graphs Topological Sort Original on LeetCode

Collect Coins in a Tree is a hard graphs problem solved with the topological sort pattern. The best approach, optimal (peel leaves layer by layer), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every start node) up.

Problem

You are given an undirected tree with n nodes labelled 0 to n - 1, described by edges, and an array coins where coins[i] is 1 if node i holds a coin and 0 otherwise.

You pick any node to start on. From then on you may, as often as you like, either pick up every coin within distance 2 of your current node (distance counts edges), or move along one edge to a neighbouring node.

Return the smallest number of edges you have to walk to pick up every coin and end on the node where you started. Walking the same edge twice counts twice.

Examples

Example 1

Input
coins = [1, 0, 0, 0, 0, 0, 1], edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
Output
4
Why
Start at 3, walk to 2 (coin 0 is now 2 away), back to 3, out to 4 (coin 6 is 2 away) and back: 4 edges.

Example 2

Input
coins = [0, 1, 1, 0, 1], edges = [[0, 1], [0, 2], [0, 3], [3, 4]]
Output
0
Why
Standing on node 0, every coin is within distance 2, so no move is needed.

Example 3

Input
coins = [0, 0, 1, 0, 0, 0, 0, 1, 0], edges = [[0, 1], [1, 2], [0, 3], [3, 4], [4, 5], [5, 6], [6, 7], [0, 8]]
Output
6
Why
Node 8 holds nothing and can be ignored. The coins sit at the two ends of the path 2-1-0-3-4-5-6-7; only the 3 middle edges 0-3-4-5 must be walked, there and back.

Constraints

  • n == coins.length, 1 <= n <= 3 * 10^4
  • coins[i] is 0 or 1
  • edges.length == n - 1, 0 <= a_i, b_i < n, a_i != b_i
  • The edges form a tree.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every start node)O(n²)O(n)
Optimal (peel leaves layer by layer)O(n)O(n)

1Brute force (try every start node)

TimeO(n²)One O(n) BFS and backward pass per start node, n start nodes.
SpaceO(n)Adjacency list, parent, order and far arrays.

Fix the start node r and root the tree there. The nodes you visit form a connected subtree containing r. A coin is collected from its ancestor two levels up, so a node v (other than r) must be visited exactly when its subtree holds a coin at least 2 levels below v (or on v itself at depth 2 or more relative to v). Count those nodes: each one costs one edge out and one edge back. Take the best start.

  1. Build an adjacency list.
  2. For each start r, BFS to get a parent array and a BFS order.
  3. Walk the order backwards and compute far[v] = the largest depth of a coin below v measured from v (-1 if none, 0 if v itself has a coin).
  4. Count nodes v != r with far[v] >= 2; the cost for this start is 2 * count.
  5. Return the minimum cost over all starts.
class Solution {
    public 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<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int best = Integer.MAX_VALUE;
        int[] parent = new int[n], order = new int[n], far = new int[n];
        for (int r = 0; r < n; r++) {
            boolean[] seen = new boolean[n];
            int head = 0, tail = 0;
            order[tail++] = r;
            seen[r] = true;
            parent[r] = -1;
            while (head < tail) {
                int v = order[head++];
                for (int u : adj.get(v)) {
                    if (!seen[u]) {
                        seen[u] = true;
                        parent[u] = v;
                        order[tail++] = u;
                    }
                }
            }
            for (int i = 0; i < n; i++) far[i] = coins[i] == 1 ? 0 : -1;
            int count = 0;
            for (int i = n - 1; i >= 1; i--) {
                int v = order[i];
                if (far[v] >= 2) count++;
                if (far[v] >= 0) far[parent[v]] = Math.max(far[parent[v]], far[v] + 1);
            }
            best = Math.min(best, 2 * count);
        }
        return best;
    }
}

2Optimal (peel leaves layer by layer)

TimeO(n)Each node is removed at most once and each edge is looked at a constant number of times; the two extra rounds scan the nodes once each.
SpaceO(n)Adjacency lists, degrees, the removed flags and the queue.

Shrink the tree to the part you really have to walk. First repeatedly delete leaves that hold no coin; they can never matter. Now every leaf has a coin, and a coin is picked up from two edges away, so delete the current leaves once, then the new leaves once more. The nodes still standing form a connected subtree that must be fully walked, each edge out and back, so the answer is 2 * (remaining nodes - 1), or 0 if at most one node is left.

  1. Build adjacency lists and a degree array.
  2. Queue every leaf (degree 1) without a coin. Pop a node, mark it removed and lower its live neighbours' degrees; a neighbour that drops to degree 1 and has no coin joins the queue.
  3. Twice: collect all live nodes with degree 1, remove them all and lower their live neighbours' degrees.
  4. Let left be the number of live nodes; return 2 * max(0, left - 1).
class Solution {
    public 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]]++;
        }
        boolean[] removed = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (deg[v] == 1 && coins[v] == 0) queue.add(v);
        }
        while (!queue.isEmpty()) {
            int v = queue.poll();
            removed[v] = true;
            for (int u : adj.get(v)) {
                if (!removed[u]) {
                    deg[u]--;
                    if (deg[u] == 1 && coins[u] == 0) queue.add(u);
                }
            }
        }
        for (int round = 0; round < 2; round++) {
            List<Integer> leaves = new ArrayList<>();
            for (int v = 0; v < n; v++) {
                if (!removed[v] && deg[v] == 1) leaves.add(v);
            }
            for (int v : leaves) {
                removed[v] = true;
                for (int u : adj.get(v)) {
                    if (!removed[u]) deg[u]--;
                }
            }
        }
        int left = 0;
        for (int v = 0; v < n; v++) {
            if (!removed[v]) left++;
        }
        return 2 * Math.max(0, left - 1);
    }
}

Edge cases to test

  • No coins at all: the answer is 0
  • A single node, or a tree where every coin is within distance 2 of one node: the answer is 0
  • Long coinless branches that must never be walked
  • A coin on a leaf at the end of a long path

Hints

Hint 1

A leaf without a coin is never worth visiting. Remove it, and repeat: its neighbour may become a coinless leaf too.

Hint 2

After that, every leaf holds a coin. Since a coin is collected from 2 steps away, the last two layers of leaves never need to be stepped on.

Hint 3

Whatever remains is a connected subtree you must walk completely: every edge twice, once out and once back.

FAQ

What is the best time complexity for Collect Coins in a Tree?

Optimal (peel leaves layer by layer) runs in O(n) time and O(n) extra space. Each node is removed at most once and each edge is looked at a constant number of times; the two extra rounds scan the nodes once each.

Which pattern does Collect Coins in a Tree use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Collect Coins in a Tree?

Yes. Brute force (try every start node) takes O(n²) time and O(n) space. Fix the start node r and root the tree there.

Which edge cases should I test for Collect Coins in a Tree?

No coins at all: the answer is 0; A single node, or a tree where every coin is within distance 2 of one node: the answer is 0; Long coinless branches that must never be walked; A coin on a leaf at the end of a long path.