#2603

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Collect Coins in a Tree

The "Collect Coins in a Tree" problem requires traversing a tree to collect coins in the fewest steps while returning to the starting node.

array tree graph topological sort

Problem Statement

Given an undirected tree with n nodes and a list of edges connecting them, each node may or may not have a coin. You need to start from any node and traverse the tree to collect all the coins, ensuring you return to your starting point. A coin is present at node i if coins[i] = 1, otherwise coins[i] = 0.

Your task is to determine the minimum number of edges you need to traverse to collect all coins and return to the initial node. You may perform multiple traversals if needed, but must find the optimal path in terms of the number of edges.

Examples

Example 1

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

Output: 2

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

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.length
1 <= n <= 3 * 104
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.

Solution Approach

Graph Traversal with DFS

Use depth-first search (DFS) to explore the tree from any node. Track which nodes have coins, and prune branches that do not contribute to the solution. This approach ensures that only relevant paths are considered.

Pruning Unnecessary Nodes

Nodes without coins and their leaves can be ignored in the traversal to reduce the overall complexity. By pruning redundant parts of the tree, the algorithm focuses only on necessary nodes and edges.

Topological Sort for Optimization

Leverage topological sorting combined with graph indegree calculations to optimize the DFS traversal. This ensures that all paths are explored efficiently without redundant operations, leading to minimal traversal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach chosen, but typically a DFS with pruning will run in O(n) time, where n is the number of nodes. The space complexity will also be O(n) due to the recursive stack and storage of visited nodes and coin positions.

What Interviewers Usually Probe

Looks for understanding of tree traversal and pruning techniques.
Evaluates candidate's ability to optimize graph traversal through topological ordering.
Assesses if the candidate can identify redundant nodes and edges in tree problems.

Common Pitfalls or Variants

Common pitfalls

Failing to prune unnecessary nodes that don't affect the coin collection.
Not considering optimal traversal order leading to redundant path explorations.
Overlooking the fact that all leaf nodes without coins are irrelevant to the problem.

Follow-up variants

Variation 1: The tree is directed and includes cycles.
Variation 2: The tree is rooted and requires a specific root for traversal.
Variation 3: Add restrictions on the number of times you can traverse an edge.

FAQ

What is the core pattern of the "Collect Coins in a Tree" problem?

The core pattern is optimizing tree traversal by using graph indegree calculations and topological sorting, along with pruning unnecessary nodes.

How do I know which nodes to prune in the "Collect Coins in a Tree" problem?

Prune leaf nodes that do not contain coins. These nodes do not contribute to the solution and can be safely ignored during traversal.

What is the significance of topological sorting in this problem?

Topological sorting helps order the nodes in such a way that the DFS traversal is optimized, ensuring that only relevant paths are explored.

What should I focus on to minimize the traversal in "Collect Coins in a Tree"?

Focus on identifying nodes with coins, pruning unnecessary branches, and using efficient traversal strategies like DFS with topological sorting.

Can this problem be solved without pruning the tree?

It is possible but inefficient. Pruning irrelevant nodes significantly reduces the time complexity of the solution.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        g = defaultdict(set)
        for a, b in edges:
            g[a].add(b)
            g[b].add(a)
        n = len(coins)
        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)
        while q:
            i = q.popleft()
            for j in g[i]:
                g[j].remove(i)
                if coins[j] == 0 and len(g[j]) == 1:
                    q.append(j)
            g[i].clear()
        for k in range(2):
            q = [i for i in range(n) if len(g[i]) == 1]
            for i in q:
                for j in g[i]:
                    g[j].remove(i)
                g[i].clear()
        return sum(len(g[a]) > 0 and len(g[b]) > 0 for a, b in edges) * 2

Continue Practicing

#2246 longest path with different adjacent characters #2646 minimize the total price of the trips #2467 most profitable path in a tree