#2973

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Find Number of Coins to Place in Tree Nodes

Determine the exact number of coins to place on each tree node using subtree cost products and DFS tracking.

dynamic programming tree depth first search sorting heap priority queue

Problem Statement

You are given an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. The tree is represented as a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates an edge connecting nodes ai and bi. Each node has an associated integer cost given in an array cost of length n.

Your task is to place coins on every node. For each node, calculate the number of coins as the maximum product of up to three largest positive costs in its subtree or the minimum product of up to three non-positive costs, ensuring each node gets the correct number of coins according to its subtree structure.

Examples

Example 1

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

Output: [120,1,1,1,1,1]

For node 0 place 6 * 5 * 4 = 120 coins. All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 2

Input: edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2]

Output: [280,140,32,1,1,1,1,1,1]

The coins placed on each node are:

Place 8 * 7 * 5 = 280 coins on node 0.
Place 7 * 5 * 4 = 140 coins on node 1.
Place 8 * 2 * 2 = 32 coins on node 2.
All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 3

Input: edges = [[0,1],[0,2]], cost = [1,2,-2]

Output: [0,1,1]

Node 1 and 2 are leaves with subtree of size 1, place 1 coin on each of them. For node 0 the only possible product of cost is 2 * 1 * -2 = -4. Hence place 0 coins on node 0.

Constraints

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
cost.length == n
1 <= |cost[i]| <= 104
The input is generated such that edges represents a valid tree.

Solution Approach

Depth-First Search Traversal

Use DFS to explore the tree from the root. For each node, collect costs from all children and the node itself. Track the largest three positive and smallest three non-positive costs to handle the subtree product computation accurately.

Subtree Cost Calculation

At each node, compute the possible products of the top three positive costs and the smallest three non-positive costs. Choose the product that is non-negative and maximal to assign the number of coins. If all products are negative, assign zero coins to avoid invalid placements.

Dynamic Programming with State Tracking

Store intermediate results for each subtree in a DP array or dictionary to prevent recomputation. Each node's state includes its top three positive costs and smallest three non-positive costs, enabling efficient upward aggregation and correct coin assignment.

Complexity Analysis

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

Time complexity is O(n) for traversing all nodes once with DFS and aggregating subtree costs. Space complexity is O(n) for storing children and cost tracking arrays in each node's state during traversal.

What Interviewers Usually Probe

Candidate considers DFS for full tree traversal and subtree aggregation.
Candidate identifies that leaf nodes always receive one coin as a base case.
Candidate correctly handles negative and zero costs in product calculation to avoid incorrect coin counts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle negative and zero costs leading to wrong coin numbers.
Incorrectly tracking fewer than three largest/smallest costs, causing wrong product computation.
Failing to store subtree results, resulting in repeated calculations and timeouts on large trees.

Follow-up variants

Compute coins using sum instead of product of subtree costs.
Find maximum coin placement in weighted n-ary trees instead of binary trees.
Determine minimum coins with modified rules for negative-only subtrees.

FAQ

What pattern does this problem primarily test?

It focuses on binary-tree traversal and state tracking, requiring DFS combined with subtree cost aggregation.

How do I handle negative costs when placing coins?

Track the smallest three non-positive costs and compute their product. If all products are negative, assign zero coins to that node.

Can this approach handle large trees efficiently?

Yes, using DFS with dynamic programming on each subtree keeps time complexity linear in the number of nodes.

Why do leaf nodes always get one coin?

Leaf nodes have a subtree size of one, so the maximum or minimum product of costs defaults to 1 coin placement.

Does GhostInterview provide step-by-step guidance for this problem?

Yes, it shows exactly how to traverse the tree, track positive and non-positive costs, and compute coin placement correctly for every node.

terminal

Solution

Solution 1: DFS + Sorting

According to the problem description, there are two situations for the number of coins placed at each node $a$:

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 placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
        def dfs(a: int, fa: int) -> List[int]:
            res = [cost[a]]
            for b in g[a]:
                if b != fa:
                    res.extend(dfs(b, a))
            res.sort()
            if len(res) >= 3:
                ans[a] = max(res[-3] * res[-2] * res[-1], res[0] * res[1] * res[-1], 0)
            if len(res) > 5:
                res = res[:2] + res[-3:]
            return res

        n = len(cost)
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        ans = [1] * n
        dfs(0, -1)
        return ans

Continue Practicing

#2925 maximum score after applying operations on a tree #2920 maximum points after collecting coins from all nodes #3068 find the maximum sum of node values