Find Number of Coins to Place in Tree Nodes - Video Solutions
FIND NUMBER OF COINS TO PLACE IN BINARY TREE NODES | LEETCODE 2973 | PYTHON DFS + HEAP SOLUTION
Find Number of Coins to Place in Tree Nodes - Video Solution
Watch 5 video solutions for Find Number of Coins to Place in Tree Nodes, a hard level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Cracking FAANG has 1,574 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are also given a 0-indexed integer array cost of length n, where cost[i] is the cost assigned to the ith node.
You need to place some coins on every node of the tree. The number of coins to be placed at node i can be calculated as:
- If size of the subtree of node
iis less than3, place1coin. - Otherwise, place an amount of coins equal to the maximum product of cost values assigned to
3distinct nodes in the subtree of nodei. If this product is negative, place0coins.
Return an array coin of size n such that coin[i] is the number of coins placed at node i.
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] Explanation: 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] Explanation: 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] Explanation: 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 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < ncost.length == n1 <= |cost[i]| <= 104- The input is generated such that
edgesrepresents a valid tree.
Approach Overview
Problem Overview: You are given a tree where each node has an integer value. For every node, compute how many coins should be placed on it based on the maximum product of any three values inside that node's subtree. If the subtree has fewer than three nodes, the result is 1. The challenge is efficiently aggregating subtree values while traversing the tree.
Approach 1: DFS with Sorting (O(n log k) time, O(n) space)
Run a Depth-First Search from the root and collect values from each subtree. At every node, maintain a list of candidate values from its children plus its own value. Sort the collected values and compute the maximum product using the largest three numbers or two smallest negatives with the largest positive. Since only a few extreme values matter, you typically keep the top three maximum values and bottom two minimum values after sorting. The product is assigned to the node if the subtree has at least three nodes; otherwise return 1. This approach is straightforward to implement and works well because the candidate list stays very small.
Approach 2: DFS with Priority Queue (O(n log k) time, O(n) space)
This variant replaces sorting with heaps. During the tree traversal, each DFS call maintains two structures: a max-oriented structure for the largest values and a min-oriented structure for the smallest negatives. While merging child results, push values into the heaps and keep only the few extremes required to evaluate the product. After gathering candidates for a node, compute the best product using either the three largest numbers or the combination of two smallest negatives and the largest positive. Using a priority queue avoids repeated sorting and keeps updates efficient when merging multiple children.
Recommended for interviews: The DFS aggregation approach with tracked extremes is what interviewers expect. It shows you understand subtree dynamic programming and how to propagate only the necessary information upward. A naive solution that collects all subtree values demonstrates the idea, but maintaining only the top three maximums and bottom two minimums proves you can optimize both time and memory.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Sorting | O(n log k) | O(n) | Simple implementation when only a few extreme values are kept per subtree |
| DFS with Priority Queue | O(n log k) | O(n) | Useful when merging many child subtrees and you want structured access to extremes |