Find Number of Coins to Place in Tree Nodes solution and explanation
4 more videos on this problem
FIND NUMBER OF COINS TO PLACE IN BINARY TREE NODES | LEETCODE 2973 | PYTHON DFS + HEAP SOLUTIONCracking FAANG · 24:59 · 1K views
Find Number of Coins to Place in Tree Nodes | Leetcode Biweekly 120codingMohan · 24:16 · 1K views
2973 | Find Number of Coins to Place in Tree Nodes | Bi-Weekly Contest 120 | Leetcode HardHarsit Sinha · 25:18 · 375 views
Find Number of Coins to Place in Tree Nodes (Leetcode Biweekly 120)Soumya Bhattacharjee · 10:39 · 292 views
2973. Find Number of Coins to Place in Tree Nodes (Leetcode Hard)Programming Live with Larry · 25:58 · 246 views
The problem
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.
Approach 1: DFS with Sorting
The idea is to use Depth First Search (DFS) to calculate the size of each subtree and find the maximum cost product using sorting for the top 3 values.
We can use a DFS traversal to calculate the size of the subtree for each node. If the size is less than 3, place 1 coin. Otherwise, collect all costs in the given subtree, sort the costs, and compute the maximum product of the top 3 values. This approach ensures optimized computation by leveraging the sorting step on potentially large subtrees.
from collections import defaultdict
class Solution:
def findCoins(self, edges, cost):
def dfs(node, parent):
subtree_costs = []
for neighbor in graph[node]:
if neighbor != parent:
dfs(neighbor, node)
subtree_costs.append(cost[neighbor])
if len(subtree_costs) < 2:
coins[node] = 1
else:
subtree_costs.sort(reverse=True)
max_product = subtree_costs[0] * subtree_costs[1] * subtree_costs[2]
coins[node] = max(max_product, 0)
n = len(cost)
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
coins = [0] * n
dfs(0, -1)
return coins
# Example run
e = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
c = [1, 2, 3, 4, 5, 6]
solution = Solution()
print(solution.findCoins(e, c))import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TreeCoins {
public static void main(String[] args) {
int n = 6;
int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}};
int[] cost = {1, 2, 3, 4, 5, 6};
List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
for (int[] edge : edges) {
tree.get(edge[0]).add(edge[1]);
tree.get(edge[1]).add(edge[0]);
}
int[] coins = new int[n];
new TreeCoins().dfs(0, -1, tree, cost, coins);
for (int coin : coins) {
System.out.print(coin + " ");
}
}
private void dfs(int node, int parent, List<List<Integer>> tree, int[] cost, int[] coins) {
List<Integer> subtreeCosts = new ArrayList<>();
for (int neighbor : tree.get(node)) {
if (neighbor != parent) {
dfs(neighbor, node, tree, cost, coins);
subtreeCosts.add(cost[neighbor]);
}
}
if (subtreeCosts.size() < 2) {
coins[node] = 1;
} else {
Collections.sort(subtreeCosts, Collections.reverseOrder());
int maxProduct = subtreeCosts.get(0) * subtreeCosts.get(1) * subtreeCosts.get(2);
coins[node] = maxProduct > 0 ? maxProduct : 0;
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void dfs(int node, int parent, vector<vector<int>>& tree, vector<int>& cost, vector<int>& coins) {
vector<int> subtreeCosts;
for (int neighbor : tree[node]) {
if (neighbor != parent) {
dfs(neighbor, node, tree, cost, coins);
subtreeCosts.push_back(cost[neighbor]);
}
}
if (subtreeCosts.size() < 2) {
coins[node] = 1;
} else {
sort(subtreeCosts.begin(), subtreeCosts.end(), greater<int>());
int maxProduct = subtreeCosts[0] * subtreeCosts[1] * subtreeCosts[2];
coins[node] = maxProduct > 0 ? maxProduct : 0;
}
}
int main() {
int n = 6;
vector<vector<int>> edges = {{0,1},{0,2},{0,3},{0,4},{0,5}};
vector<int> cost = {1,2,3,4,5,6};
vector<vector<int>> tree(n);
for (auto& edge : edges) {
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]);
}
vector<int> coins(n, 0);
dfs(0, -1, tree, cost, coins);
for (int coin : coins) {
cout << coin << ' ';
}
cout << endl;
return 0;
}function calculateCoins(n, edges, cost) {
const tree = Array.from({ length: n }, () => []);
for (let [a, b] of edges) {
tree[a].push(b);
tree[b].push(a);
}
const coins = new Array(n).fill(0);
function dfs(node, parent) {
const subtreeCosts = [];
for (let neighbor of tree[node]) {
if (neighbor !== parent) {
dfs(neighbor, node);
subtreeCosts.push(cost[neighbor]);
}
}
if (subtreeCosts.length < 2) {
coins[node] = 1;
} else {
subtreeCosts.sort((a, b) => b - a);
const maxProduct = subtreeCosts[0] * subtreeCosts[1] * subtreeCosts[2];
coins[node] = maxProduct > 0 ? maxProduct : 0;
}
}
dfs(0, -1);
return coins;
}
// Example usage
const edges = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]];
const cost = [1, 2, 3, 4, 5, 6];
console.log(calculateCoins(6, edges, cost));#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXN 20000
int adj[MAXN][MAXN];
int size[MAXN];
int coin[MAXN];
void dfs(int node, int parent, int cost[]) {
int subtreeCost[MAXN];
int scIndex = 0;
for (int i = 0; i < size[node]; i++) {
int nextNode = adj[node][i];
if (nextNode != parent) {
dfs(nextNode, node, cost);
subtreeCost[scIndex++] = cost[nextNode];
}
}
// Calculate coins to place
if (scIndex < 2) {
coin[node] = 1;
} else {
qsort(subtreeCost, scIndex, sizeof(int), compare); // Sort descending
int maxProduct = subtreeCost[0] * subtreeCost[1] * subtreeCost[2];
coin[node] = maxProduct > 0 ? maxProduct : 0;
}
}
int compare(const void *a, const void *b) {
return (*(int *)b) - (*(int *)a);
}
int main() {
int n = 6;
int edges[5][2] = {{0,1}, {0,2}, {0,3}, {0,4}, {0,5}};
int cost[6] = {1,2,3,4,5,6};
for (int i = 0; i < n - 1; i++) {
int a = edges[i][0];
int b = edges[i][1];
adj[a][size[a]++] = b;
adj[b][size[b]++] = a;
}
dfs(0, -1, cost);
for (int i = 0; i < n; i++) printf("%d ", coin[i]);
printf("\n");
return 0;
}using System;
using System.Collections.Generic;
public class TreeCoins {
public static void Main() {
int n = 6;
int[][] edges = new int[][] {
new int[] {0, 1}, new int[] {0, 2}, new int[] {0, 3}, new int[] {0, 4}, new int[] {0, 5}
};
int[] cost = new int[] {1, 2, 3, 4, 5, 6};
var tree = new List<int>[n];
for (int i = 0; i < n; i++)
tree[i] = new List<int>();
foreach (var edge in edges) {
tree[edge[0]].Add(edge[1]);
tree[edge[1]].Add(edge[0]);
}
var coins = new int[n];
DFS(0, -1, tree, cost, coins);
foreach (var coin in coins)
Console.Write(coin + " ");
}
private static void DFS(int node, int parent, List<int>[] tree, int[] cost, int[] coins) {
var subtreeCosts = new List<int>();
foreach (var neighbor in tree[node]) {
if (neighbor != parent) {
DFS(neighbor, node, tree, cost, coins);
subtreeCosts.Add(cost[neighbor]);
}
}
if (subtreeCosts.Count < 2) {
coins[node] = 1;
} else {
subtreeCosts.Sort((a, b) => b.CompareTo(a));
int maxProduct = subtreeCosts[0] * subtreeCosts[1] * subtreeCosts[2];
coins[node] = maxProduct > 0 ? maxProduct : 0;
}
}
}This Python solution utilizes a defaultdict for adjacency representation and a DFS traversal to perform a postorder evaluation. It sorts the gathered costs for each node, tracks back to construct coins assignment following the logic of subtree size and cost product evaluation.
Time Complexity: O(n log n), driven by sort operations on subtree costs.
Space Complexity: O(n), required for graph and observed values in memory.
Approach 2: DFS with Priority Queue
This approach uses a priority queue (or max-heap) to track the top 3 largest values in each node's subtree. During the DFS traversal, instead of sorting the entire subtree costs, we maintain the top 3 maximum costs in the heap. This approach is slightly more efficient in scenarios where sorting can be avoided.
import heapq
class Solution:
def findCoins(self, edges, cost):
def dfs(node, parent):
pq = []
for neighbor in graph[node]:
if neighbor != parent:
dfs(neighbor, node)
heapq.heappush(pq, cost[neighbor])
if len(pq) > 3:
heapq.heappop(pq)
if len(graph[node]) <= 1:
coins[node] = 1
else:
if len(pq) < 3:
coins[node] = 0
else:
coins[node] = max(0, pq[0] * pq[1] * pq[2])
n = len(cost)
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
coins = [0] * n
dfs(0, -1)
return coins
# Example run
e = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
c = [1, 2, 3, 4, 5, 6]
solution = Solution()
print(solution.findCoins(e, c))import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class TreeCoins {
public static void main(String[] args) {
int n = 6;
int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}};
int[] cost = {1, 2, 3, 4, 5, 6};
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
for (int[] edge : edges) {
tree.get(edge[0]).add(edge[1]);
tree.get(edge[1]).add(edge[0]);
}
int[] coins = new int[n];
new TreeCoins().dfs(0, -1, tree, cost, coins);
for (int coin : coins) {
System.out.print(coin + " ");
}
}
private void dfs(int node, int parent, ArrayList<ArrayList<Integer>> tree, int[] cost, int[] coins) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int neighbor : tree.get(node)) {
if (neighbor != parent) {
dfs(neighbor, node, tree, cost, coins);
pq.offer(cost[neighbor]);
if (pq.size() > 3) pq.poll();
}
}
if (tree.get(node).size() <= 1) {
coins[node] = 1;
} else {
if (pq.size() < 3) {
coins[node] = 0;
} else {
int maxProduct = 1;
while (!pq.isEmpty()) {
maxProduct *= pq.poll();
}
coins[node] = Math.max(maxProduct, 0);
}
}
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void dfs(int node, int parent, vector<vector<int>>& tree, vector<int>& cost, vector<int>& coins) {
priority_queue<int> pq; // max-heap
for (int neighbor : tree[node]) {
if (neighbor != parent) {
dfs(neighbor, node, tree, cost, coins);
pq.push(cost[neighbor]);
if (pq.size() > 3) pq.pop();
}
}
if (tree[node].size() <= 1) { // for tree node with less than 2 children
coins[node] = 1;
} else {
vector<int> top3;
while (!pq.empty()) {
top3.push_back(pq.top());
pq.pop();
}
int maxProduct = top3[0] * top3[1] * top3[2];
coins[node] = maxProduct > 0 ? maxProduct : 0;
}
}
int main() {
int n = 6;
vector<vector<int>> edges = {{0,1},{0,2},{0,3},{0,4},{0,5}};
vector<int> cost = {1,2,3,4,5,6};
vector<vector<int>> tree(n);
for (auto& edge : edges) {
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]);
}
vector<int> coins(n);
dfs(0, -1, tree, cost, coins);
for (int coin : coins) {
cout << coin << " ";
}
cout << endl;
return 0;
}This Python solution integrates a min-heap to maintain a rolling tally of the top 3 costs for each node. It uses the `heapq` module to efficiently handle the necessary heap operations.
Time Complexity: O(n), because each heap operation is limited to top 3 elements.
Space Complexity: O(n), considering heap management and recursion depth.
Approach 3: DFS + Sorting
According to the problem description, there are two situations for the number of coins placed at each node a:
- If the number of nodes in the subtree corresponding to node
ais less than3, then place1coin; - If the number of nodes in the subtree corresponding to node
ais greater than or equal to3, then we need to take out3different nodes from the subtree, calculate the maximum value of their cost product, and then place the corresponding number of coins at nodea. If the maximum product is negative, place0coins.
The first situation is relatively simple, we just need to count the number of nodes in the subtree of each node during the traversal.
For the second situation, if all costs are positive, we should take the 3 nodes with the largest costs; if there are negative costs, we should take the 2 nodes with the smallest costs and the 1 node with the largest cost. Therefore, we need to maintain the smallest 2 costs and the largest 3 costs in each subtree.
We first construct the adjacency list g based on the given two-dimensional array edges, where g[a] represents all neighbor nodes of node a.
Next, we design a function dfs(a, fa), which returns an array res, which stores the smallest 2 costs and the largest 3 costs in the subtree of node a (may not be 5).
In the function dfs(a, fa), we add the cost cost[a] of node a to the array res, and then traverse all neighbor nodes b of node a. If b is not the parent node fa of node a, then we add the result of dfs(b, a) to the array res.
Then, we sort the array res, and then calculate the number of coins placed at node a based on the length m of the array res, and update ans[a]:
- If
m \ge 3, then the number of coins placed at nodeaismax(0, res[m - 1] times res[m - 2] times res[m - 3], res[0] times res[1] times res[m - 1]), otherwise the number of coins placed at nodeais1; - If
m > 5, then we only need to keep the first2elements and the last3elements of the arrayres.
Finally, we call the function dfs(0, -1), and return the answer array ans.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of nodes.
function placedCoins(edges: number[][], cost: number[]): number[] {
const n = cost.length;
const ans: number[] = Array(n).fill(1);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const dfs = (a: number, fa: number): number[] => {
const res: number[] = [cost[a]];
for (const b of g[a]) {
if (b !== fa) {
res.push(...dfs(b, a));
}
}
res.sort((a, b) => a - b);
const m = res.length;
if (m >= 3) {
const x = res[m - 1] * res[m - 2] * res[m - 3];
const y = res[0] * res[1] * res[m - 1];
ans[a] = Math.max(0, x, y);
}
if (m > 5) {
res.splice(2, m - 5);
}
return res;
};
dfs(0, -1);
return ans;
}func placedCoins(edges [][]int, cost []int) []int64 {
n := len(cost)
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
ans := make([]int64, n)
for i := range ans {
ans[i] = int64(1)
}
var dfs func(a, fa int) []int
dfs = func(a, fa int) []int {
res := []int{cost[a]}
for _, b := range g[a] {
if b != fa {
res = append(res, dfs(b, a)...)
}
}
sort.Ints(res)
m := len(res)
if m >= 3 {
x := res[m-1] * res[m-2] * res[m-3]
y := res[0] * res[1] * res[m-1]
ans[a] = max(0, int64(x), int64(y))
}
if m >= 5 {
res = append(res[:2], res[m-3:]...)
}
return res
}
dfs(0, -1)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Sorting | Time Complexity: O(n log n), driven by sort operations on subtree costs. |
| DFS with Priority Queue | Time Complexity: O(n), because each heap operation is limited to top 3 elements. |
| DFS + Sorting | – |
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 |
Frequently asked questions
Is Find Number of Coins to Place in Tree Nodes easy or hard?
The problem is classified as Hard on LeetCode because it combines tree traversal with careful value aggregation. The main difficulty comes from recognizing that only a few extreme values in each subtree affect the maximum product. Once that insight is clear, the implementation becomes a manageable DFS dynamic programming pattern.
Find Number of Coins to Place in Tree Nodes Python/Java solution
Python and Java solutions typically implement DFS over the adjacency list and return a small list of candidate values for each subtree. After combining child results, the algorithm computes the best product and stores it for the current node. The same logic translates directly to C++, Java, and other languages.
How to solve Find Number of Coins to Place in Tree Nodes in O(n)?
Traverse the tree using DFS and compute results bottom‑up. Each node returns a small set of candidate values from its subtree: the three largest and two smallest numbers. Using these extremes, compute the maximum product either from the three largest values or from two negatives and the largest positive. Propagate the reduced candidate set to the parent so the traversal stays linear.
What is the best approach for Find Number of Coins to Place in Tree Nodes?
The most effective approach is a DFS-based subtree dynamic programming solution. During traversal, keep only the top three maximum values and bottom two minimum values from each subtree. These extremes are enough to compute the maximum product of three numbers. The solution runs in O(n) traversal time with small constant factors for maintaining candidates.
Is Find Number of Coins to Place in Tree Nodes asked at Google/Amazon/Meta?
Tree DP and subtree aggregation problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. Variants often involve computing metrics over subtrees or propagating partial results during DFS. Understanding how to keep only necessary extremes is a common optimization pattern tested in these interviews.
What data structure is used in Find Number of Coins to Place in Tree Nodes?
The core structures are adjacency lists for the tree and recursion or stacks for DFS traversal. Many implementations also use arrays or small lists to track extreme values, while alternative versions use heaps or priority queues to maintain the largest and smallest numbers efficiently.
What is the time complexity of Find Number of Coins to Place in Tree Nodes?
The typical optimized solution runs in O(n) DFS traversal with small additional operations per node. When sorting or heap operations are used to maintain candidate values, the complexity is often described as O(n log k) where k is the small number of tracked values (usually ≤5). Space complexity is O(n) due to recursion stack and adjacency lists.