LeetCode 2603: Collect Coins in a Tree Solution

Master LeetCode problem 2603 (Collect Coins in a Tree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2603. Collect Coins in a Tree

Hard

Array Tree Graph Topological Sort

Problem Explanation

Explanation

To solve this problem, we can perform a depth-first search (DFS) traversal on the tree starting from each vertex as the root. For each vertex, we calculate the minimum number of edges needed to collect all the coins and return back to that vertex. We keep track of the number of coins in the subtree rooted at each vertex and the minimum distance to collect all coins in that subtree.

Algorithm

Perform a depth-first search (DFS) starting from each vertex as the root.
Calculate the number of coins in the subtree rooted at each vertex.
Calculate the minimum distance to collect all the coins in the subtree rooted at each vertex.
Update the answer with the minimum distance to collect coins from each subtree and return back to the root.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree.

Space Complexity

The space complexity of this algorithm is O(n) for storing the adjacency list and visited array.

Solution Code

class Solution {
    int ans;
    
    public int collectCoinsInTree(int[] coins, int[][] edges) {
        int n = coins.length;
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        ans = 0;
        dfs(0, -1, coins, adjList);
        return ans;
    }
    
    private int[] dfs(int u, int parent, int[] coins, List<List<Integer>> adjList) {
        int[] sub = new int[2]; // sub[0] -> total coins, sub[1] -> min distance
        sub[0] = coins[u];
        sub[1] = 0;
        for (int v : adjList.get(u)) {
            if (v != parent) {
                int[] tmp = dfs(v, u, coins, adjList);
                sub[0] += tmp[0];
                sub[1] += tmp[1] + tmp[0];
            }
        }
        ans += sub[1];
        return sub;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2603 (Collect Coins in a Tree)?

This page provides optimized solutions for LeetCode problem 2603 (Collect Coins in a Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2603 (Collect Coins in a Tree)?

The time complexity for LeetCode 2603 (Collect Coins in a Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2603 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2603 in Java, C++, or Python.

Back to LeetCode Solutions