Find Number of Coins to Place in Tree Nodes

Ah, the classic problem of finding the number of coins to place in tree nodes! It’s like trying to figure out how many snacks to bring to a party where you don’t know how many guests will show up. You want to make sure everyone gets a treat, but you also don’t want to end up with a mountain of leftover chips that will haunt you for weeks.

In this problem, you are given a tree structure (think of it as a family tree, but instead of relatives, we have nodes) and each node has a cost associated with it. Your task is to determine the maximum product of coins that can be placed in the nodes, based on the costs. Sounds simple, right? Well, it’s a bit more complicated than just throwing coins around like confetti at a New Year’s party!

Code Solution

Here’s the Java solution to the problem:

Copy Code

class ChildCost {
  public ChildCost(int cost) {
    if (cost > 0)
      maxPosCosts.add(cost);
    else
      minNegCosts.add(cost);
  }

  public void update(ChildCost childCost) {
    numNodes += childCost.numNodes;
    maxPosCosts.addAll(childCost.maxPosCosts);
    minNegCosts.addAll(childCost.minNegCosts);
    maxPosCosts.sort(Comparator.reverseOrder());
    minNegCosts.sort(Comparator.naturalOrder());
    if (maxPosCosts.size() > 3)
      maxPosCosts = maxPosCosts.subList(0, 3);
    if (minNegCosts.size() > 2)
      minNegCosts = minNegCosts.subList(0, 2);
  }

  public long maxProduct() {
    if (numNodes < 3)
      return 1;
    if (maxPosCosts.isEmpty())
      return 0;
    long res = 0;
    if (maxPosCosts.size() == 3)
      res = (long) maxPosCosts.get(0) * maxPosCosts.get(1) * maxPosCosts.get(2);
    if (minNegCosts.size() == 2)
      res = Math.max(res, (long) minNegCosts.get(0) * minNegCosts.get(1) * maxPosCosts.get(0));
    return res;
  }

  private int numNodes = 1;
  private List maxPosCosts = new ArrayList<>();
  private List minNegCosts = new ArrayList<>();
}

class Solution {
  public long[] placedCoins(int[][] edges, int[] cost) {
    final int n = cost.length;
    long[] ans = new long[n];
    List[] tree = new List[n];

    for (int i = 0; i < n; i++)
      tree[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      tree[u].add(v);
      tree[v].add(u);
    }

    dfs(tree, 0, /*prev=*/-1, cost, ans);
    return ans;
  }

  private ChildCost dfs(List[] tree, int u, int prev, int[] cost, long[] ans) {
    ChildCost res = new ChildCost(cost[u]);
    for (final int v : tree[u])
      if (v != prev)
        res.update(dfs(tree, v, u, cost, ans));
    ans[u] = res.maxProduct();
    return res;
  }
}

Approach Explanation

The code uses a depth-first search (DFS) approach to traverse the tree. Each node is represented by a ChildCost object that keeps track of the maximum positive costs and minimum negative costs. As we traverse the tree, we update these costs and calculate the maximum product of coins that can be placed in the nodes. The key here is to maintain the top three positive costs and the top two negative costs to maximize the product.

Time and Space Complexity

Real-World Example

Imagine you are organizing a charity event where you need to distribute coins to different donation boxes (nodes). Each box has a different cost associated with it, and you want to maximize the total amount collected. You can’t just throw coins into any box; you need to strategically choose which boxes to fill based on their costs. This problem is akin to that scenario, where you need to find the optimal way to distribute your coins to maximize the total amount collected.

Similar Problems

Navigation Links