2973. Find Number of Coins to Place in Tree Nodes


Problem Description

In this problem, we are working with an undirected tree (a connected acyclic graph) with n nodes, where each node is assigned a unique label from 0 to n-1, and the tree's root is node 0. We're given a list of edges that define the connections between nodes and an array cost where each element represents the cost associated with the corresponding node.

We need to determine the number of coins to place at each node. The rules for placing coins are as follows:

  1. If the subtree of a node contains less than three nodes (either because it's a leaf node or has just one child), we place exactly one coin there.
  2. If the subtree contains three or more nodes, we find the maximum product of costs from any three distinct nodes within that subtree. If this product is negative, we place zero coins; otherwise, we place a number of coins equal to this maximum product.

The goal is to return an array coin of size n, where coin[i] represents the number of coins placed at node i.

Intuition

To solve this problem, we need to walk through the tree and calculate the number of coins for each node's subtree. A Depth-First Search (DFS) can be used to traverse the tree, starting at the root node (node 0). When we visit a node, we'll consider the sizes and costs of its subtree nodes to determine the number of coins for the node.

For subtrees with less than three nodes, the situation is straightforward; we simply place one coin. However, for larger subtrees, we seek to optimize the coin count by finding the maximum product of costs using three nodes from the subtree. This involves looking at both the highest and lowest cost values, as negative costs can flip the sign of the product. Thus, we keep track of the highest three and lowest two costs in each subtree.

While any node can have multiple children, for each node, we only need to maintain the information for the smallest two and largest three costs present in its subtree after visiting all its children. These will give us enough information to calculate the maximum product for that node. We then sort those values and decide the number of coins based on the computed products, considering the edge cases where negative costs are involved.

To implement this logic efficiently, our DFS function maintains an array of costs, updating this array as we traverse the children nodes. After visiting all children, we sort this array and calculate the maximum product using either the three largest positive costs or the two smallest (which might be negative) costs and the largest cost.

Finally, after computing these products at each node, the DFS function also prunes the array of costs to contain at most five elements (the lowest two and highest three), as this is all we need for any parent nodes. This array is then returned up the call stack so that the parent nodes can similarly compute their maximum products. We initialize an answer array ans with ones to cover the subtrees of size less than three and then call the DFS function starting from the root to fill in the rest.

Learn more about Tree, Depth-First Search, Dynamic Programming, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution approach for this problem makes use of several important algorithmic concepts such as Depth-First Search (DFS) for traversing trees, sorting for maintaining orders of costs, and efficient array manipulation for pruning unnecessary elements.

The DFS algorithm is suitable for problems dealing with trees because it allows us to explore all the nodes starting from the root, going depth-wise until we reach the leaves, and then backtracking. This way, we can explore the size and the costs associated with the subtrees.

To implement the DFS and solve the problem, the following steps are taken:

  1. Adjacency List Construction:

    • An adjacency list g is constructed to represent the tree structure, which is a common data structure used to represent graphs in a memory-efficient way. For each node a, g[a] stores the list of its neighbouring nodes (children).
  2. DFS Algorithm:

    • A DFS function dfs(a, fa) is defined to return an array of costs associated with the subtree rooted at node a with the parent node fa.
    • The function first includes the cost of the current node a in the results array res.
    • Then, it iterates through all the child nodes (neighbours) b of a:
      • For each child b, if b is not the parent of a, it recursively calls dfs(b, a) to get the costs from the subtree rooted at b and appends them to res.
  3. Sorting Subtree Costs:

    • After collecting the subtree costs, res is sorted to easily find the largest and smallest cost values for the maximum product calculation.
  4. Calculating Coins:

    • Based on the sorted costs res, the number of coins to be placed at each node is computed and stored in ans[a]:
      • If the subtree size is at least 3, it takes the maximum product of the last three costs or the product of the first two and the last cost, whichever is larger (considering non-negative product), otherwise the number of coins is 1.
      • If the result is negative, 0 coins are placed.
  5. Pruning Costs Array:

    • To avoid unnecessary computation for the ancestors, the array res is pruned to keep at most the smallest two and the largest three costs — as these five values are sufficient to calculate the max product for any parent node.
  6. Initializing Ans Array:

    • An array ans of size n is initialized with ones, which caters to those nodes whose subtrees are smaller than size three.
  7. Starting DFS Traversal:

    • The DFS traversal is started from the root node 0 with an fa (parent node) of -1 (indicating no parent).
  8. Returning the Result:

    • After the full DFS traversal, the ans array filled with the number of coins for each node is returned.

By combining these steps, the solution efficiently computes the number of coins to be placed on each node in the tree by taking advantage of DFS traversal to examine each subtree, sorting to organize the costs for quick access, and intelligent array slicing for keeping only the necessary information for further computations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's go through a small example to illustrate the solution approach:

Consider a tree with n = 4 nodes and the following edge list and cost array:

  • Edges: [[0, 1], [0, 2], [1, 3]]
  • Cost: [1, -2, -3, 4]

First, we’ll create an adjacency list g to represent our tree:

1g = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

The adjacency list describes that node 0 is connected to nodes 1 and 2, node 1 is connected to 0 and 3, and so on.

Let's begin our DFS traversal with the dfs(a, fa) function, starting at the root node 0:

  1. We call dfs(0, -1) (since 0 is the root node and has no parent).

  2. Initialize res with the cost of the current node, so res = [1] (cost of node 0).

  3. We have two children to explore: 1 and 2.

    For child 1:

    • Call dfs(1, 0), since 1 has parent 0.
    • Initialize res for this call as [cost[1]] = [-2].
    • Since node 1 has one child node 3, call dfs(3, 1).
      • Initialize res in this call as [cost[3]] = [4].
      • Node 3 has no more children, so return [4] back to the parent 1.
    • Append 4 to res of node 1 and get res = [-2, 4].
    • Sort res to be [-2, 4] (negative to positive).
    • Since node 1 has a subtree with less than three nodes, it will hold 1 coin (ans[1] = 1).
    • Return [-2, 4] to the root's res.

    For child 2:

    • Node 2 has no children, so res will be [-3].
    • Since node 2 has a subtree with less than three nodes, it will hold 1 coin (ans[2] = 1).
  4. The root's res array now holds values [1, -2, 4, -3] from its own cost and its children's subtrees.

  5. We sort res to be [-3, -2, 1, 4].

  6. To find the maximum product, we consider the largest three numbers or two smallest and one large for negative products, but since the maximum product from the root's perspective is negative (-3 * -2 * 4 which is 24), we set ans[0] to be this positive product.

  7. We prune the res array for the root to only hold the necessary costs, which here will be [4] and return this to the "parent" which does not exist as 0 is the root.

After the DFS traversal is completed, the ans array looks like: [24, 1, 1, 1].

This array represents the number of coins at each node, completing our calculation using the major steps of the solution approach.

To summarize, node 0 stores 24 coins (maximum product of its subtree), while all other nodes store 1 coin each because their subtrees consist of less than three nodes.

Solution Implementation

1from typing import List
2
3class Solution:
4    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
5        # Helper function to perform DFS and compute maximum product of coin placement
6        def dfs(node: int, parent: int) -> List[int]:
7            # Start with the cost at the current node
8            node_values = [cost[node]]
9            # Explore all connected nodes (children)
10            for child in graph[node]:
11                # To prevent going back to the parent node
12                if child != parent:
13                    # Extend the list with the results from child nodes
14                    node_values.extend(dfs(child, node))
15            # Sort the values to easily find the maximum product combinations
16            node_values.sort()
17            # If there are at least 3 nodes, calculate the maximum product
18            if len(node_values) >= 3:
19                maximum_product = max(node_values[-3] * node_values[-2] * node_values[-1], 
20                                      node_values[0] * node_values[1] * node_values[-1], 0)
21                results[node] = maximum_product
22            # To optimize space, keep only the 2 smallest and 3 largest elements
23            if len(node_values) > 5:
24                node_values = node_values[:2] + node_values[-3:]
25            return node_values
26
27        # Number of nodes
28        num_nodes = len(cost)
29        # Create an adjacency list for the graph
30        graph = [[] for _ in range(num_nodes)]
31        # Build the graph using provided edges
32        for a, b in edges:
33            graph[a].append(b)
34            graph[b].append(a)
35        # Initialize answer list with a placeholder value
36        results = [1] * num_nodes
37        # Start DFS from node 0 with no parent (-1 as an indicator for no parent)
38        dfs(0, -1)
39        # Return the results which contain the maximum product for each node
40        return results
41
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Collections;
4import java.util.List;
5
6class Solution {
7    private int[] nodeCosts;
8    private List<Integer>[] graph;
9    private long[] maxProduct;
10
11    // Method to calculate the maximum product of any 3 coins placed in the tree
12    public long[] placedCoins(int[][] edges, int[] costs) {
13        int numNodes = costs.length;
14        this.nodeCosts = costs;
15        maxProduct = new long[numNodes];
16        graph = new List[numNodes];
17
18        // Initialize the maxProduct array with 1 for all nodes (default value)
19        Arrays.fill(maxProduct, 1);
20
21        // Initialize adjacency list representation of the graph
22        Arrays.setAll(graph, i -> new ArrayList<>());
23      
24        // Build the undirected graph from the edges input
25        for (int[] edge : edges) {
26            int nodeA = edge[0], nodeB = edge[1];
27            graph[nodeA].add(nodeB);
28            graph[nodeB].add(nodeA);
29        }
30
31        // Run the depth-first search starting from node 0 without a parent
32        dfs(0, -1);
33
34        return maxProduct;
35    }
36
37    private List<Integer> dfs(int node, int parent) {
38        // Create a list that will hold the costs of node's subtree, including itself
39        List<Integer> subtreeCosts = new ArrayList<>();
40        subtreeCosts.add(nodeCosts[node]);
41      
42        // Go through all neighbors of the current node
43        for (int neighbor : graph[node]) {
44            // Skip the parent to prevent going back through the tree
45            if (neighbor != parent) {
46                // Add all costs from the subtree to the current node's list
47                subtreeCosts.addAll(dfs(neighbor, node));
48            }
49        }
50
51        // Sort the node costs to easily select the three largest or smallest
52        Collections.sort(subtreeCosts);
53
54        // Calculate the product, taking care of possible overflows
55        int size = subtreeCosts.size();
56        if (size >= 3) {
57            // Get the maximum product of the 3 largest or 3 smallest costs
58            long product1 = (long) subtreeCosts.get(size - 1) * subtreeCosts.get(size - 2) * subtreeCosts.get(size - 3);
59            long product2 = (long) subtreeCosts.get(0) * subtreeCosts.get(1) * subtreeCosts.get(size - 1);
60            maxProduct[node] = Math.max(0, Math.max(product1, product2));
61        }
62
63        // Trim the list to only include the 5 largest costs if there are more than 5 elements
64        if (size >= 5) {
65            subtreeCosts = Arrays.asList(
66                subtreeCosts.get(0),
67                subtreeCosts.get(1),
68                subtreeCosts.get(size - 3),
69                subtreeCosts.get(size - 2),
70                subtreeCosts.get(size - 1)
71            );
72        }
73      
74        return subtreeCosts;
75    }
76}
77
1#include <vector>
2#include <functional>
3#include <algorithm>
4
5class Solution {
6public:
7    // Method to compute the maximum product of any three costs from the coins
8    // placed all the way to the root from each node in the tree.
9    std::vector<long long> placedCoins(std::vector<std::vector<int>>& edges, std::vector<int>& cost) {
10        int n = cost.size(); // Size of the 'cost' array.
11        std::vector<long long> ans(n, 1); // Initialize answer array with 1s.
12        std::vector<int> graph[n]; // Adjacency list representation of the graph.
13
14        // Building the graph from the edges.
15        for (auto& edge : edges) {
16            int a = edge[0], b = edge[1];
17            graph[a].push_back(b);
18            graph[b].push_back(a);
19        }
20
21        // Depth-first search function to explore the tree and calculate the products.
22        std::function<std::vector<int>(int, int)> dfs = [&](int node, int parent) -> std::vector<int> {
23            std::vector<int> result = {cost[node]}; // Start with the cost of the current node.
24            for (int neighbor : graph[node]) {
25                if (neighbor != parent) { // If the neighbor is not the parent.
26                    auto temp = dfs(neighbor, node); // DFS on the neighboring node.
27                    result.insert(result.end(), temp.begin(), temp.end()); // Merge the results.
28                }
29            }
30
31            // Sort the merged costs to find the maximum and minimum values easily.
32            std::sort(result.begin(), result.end());
33            int m = result.size(); // Size of the result after merging.
34
35            // If there are at least three nodes, calculate the maximum product of any three.
36            if (m >= 3) {
37                long long productWithMaxThree = 1LL * result[m - 1] * result[m - 2] * result[m - 3];
38                long long productWithMinTwoMaxOne = 1LL * result[0] * result[1] * result[m - 1];
39                ans[node] = std::max({0LL, productWithMaxThree, productWithMinTwoMaxOne});
40            }
41
42            // Keep only up to five elements: the three maximum and the two minimum.
43            if (m >= 5) {
44                result = {result[0], result[1], result[m - 1], result[m - 2], result[m - 3]};
45            }
46
47            return result;
48        };
49
50        // Start DFS from node 0, considering it has no parent.
51        dfs(0, -1);
52        return ans;
53    }
54};
55
1// Places coins on nodes based on the provided edges and costs, then calculates combinations of costs.
2// @param {number[][]} edges - Connections between nodes in the graph.
3// @param {number[]} cost - The cost associated with each node.
4// Returns an array representing the maximum possible product of the costs of any 3 connected nodes for each node.
5function placedCoins(edges: number[][], cost: number[]): number[] {
6    // The total number of nodes in the graph.
7    const numNodes = cost.length;
8    // Array to store the maximum product of costs for each node.
9    const maxProduct: number[] = Array(numNodes).fill(1);
10    // Graph represented as adjacency lists.
11    const graph: number[][] = Array.from({ length: numNodes }, () => []);
12    // Build the graph using the given edges.
13    for (const [node1, node2] of edges) {
14        graph[node1].push(node2);
15        graph[node2].push(node1);
16    }
17
18    // Depth-First Search function to explore the graph and calculate max products.
19    // @param {number} currNode - The current node being visited.
20    // @param {number} parentNode - The previous node from which the current node is visited.
21    // Returns the sorted costs of the current node and its descendants (max 5 elements).
22    const dfs = (currNode: number, parentNode: number): number[] => {
23        // Array to hold the cost of current node and its descendants.
24        const currCosts: number[] = [cost[currNode]];
25        // Explore all connected nodes.
26        for (const adjacentNode of graph[currNode]) {
27            if (adjacentNode !== parentNode) {
28                // Combine costs from children.
29                currCosts.push(...dfs(adjacentNode, currNode));
30            }
31        }
32        // Sort the costs in ascending order.
33        currCosts.sort((a, b) => a - b);
34        // Count of costs gathered.
35        const numCosts = currCosts.length;
36      
37        // Calculate maximum product for the current node if it has 3 or more costs.
38        if (numCosts >= 3) {
39            // Calculate products of 3 largest costs and 2 smallest with the largest cost.
40            const productTop3 = currCosts[numCosts - 1] * currCosts[numCosts - 2] * currCosts[numCosts - 3];
41            const productBottom2Top1 = currCosts[0] * currCosts[1] * currCosts[numCosts - 1];
42            // Find the maximum product.
43            maxProduct[currNode] = Math.max(productTop3, productBottom2Top1);
44        }
45        // Trim the list to keep the costs array of manageable size (max 5).
46        if (numCosts > 5) {
47            currCosts.splice(2, numCosts - 5);
48        }
49        return currCosts;
50    };
51
52    // Start the DFS from node 0 with no parent node.
53    dfs(0, -1);
54    // Return the resulting maximum products.
55    return maxProduct;
56}
57

Time and Space Complexity

The time complexity of the code can be analyzed based on the operations performed in the dfs function which is recursively called for each node. Within the dfs function, the sort method is called on the result list. The sort operation has a time complexity of O(k * log k) where k is the length of the list being sorted. As the solution keeps the result list with at most 5 elements after each call, sorting operations persist as O(1) constant time since it does not depend on n. However, the sorting operation is performed once for every node, resulting in a time complexity of O(n).

The algorithm involves a traversal over all edges exactly once, and thus the dfs function is called once per node, leading to an overall time complexity of O(n), where n is the number of nodes. The provided reference claiming a time complexity of O(n * log n) may assume a non-optimized scenario where all subtree outcomes are sorted, which does not hold in this optimized implementation.

Regarding the space complexity, the code utilizes additional data structures such as g which is an adjacency list representation of the graph, and ans which stores the result for each node. Both structures are of size O(n), matching the number of nodes. The recursion stack will at most grow to O(n) in case of a degenerate tree (a tree where each parent has only one child). Thus, the space complexity of the code is O(n), where O(n) is due to the storage of graph structure and results, and the O(n) recursion stack space in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄