We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Number of Coins to Place in Tree Nodes

Difficulty: Hard

Problem Description

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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 i-th 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 i is less than 3, place 1 coin.
  • Otherwise, place an amount of coins equal to the maximum product of cost values assigned to 3 distinct nodes in the subtree of node i. If this product is negative, place 0 coins. Return an array coin of size n such that coin[i] is the number of coins placed at node i.

Key Insights

  • The problem involves calculating subtree sizes and maximizing the product of costs for certain nodes.
  • A depth-first search (DFS) approach can efficiently traverse the tree and compute the required values.
  • Use a max-heap or sorting to find the top three costs required for the maximum product.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting or heap operations for finding the maximum product. Space Complexity: O(n) - for storing the tree structure and additional data during traversal.

Solution

We can solve this problem using a depth-first search (DFS) approach. The algorithm will traverse the tree from the root node, calculating the size of each subtree as well as the maximum product of three costs from the nodes in the subtree. For each node:

  1. If the size of the subtree is less than 3, we place 1 coin.
  2. If the size is 3 or more, we gather the costs of the nodes in the subtree, sort them, and compute the maximum product of the top three costs. If the product is negative, we place 0 coins.

We can represent the tree using an adjacency list to facilitate the traversal.

Code Solutions

def findCoins(edges, cost):
    from collections import defaultdict
    import heapq

    # Build the tree
    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)

    n = len(cost)
    coin = [0] * n
    visited = [False] * n
    
    def dfs(node):
        visited[node] = True
        subtree_costs = []
        subtree_size = 1

        for neighbor in tree[node]:
            if not visited[neighbor]:
                size, costs = dfs(neighbor)
                subtree_size += size
                subtree_costs.extend(costs)

        # At the end of each DFS call, calculate coins for this node
        if subtree_size < 3:
            coin[node] = 1
        else:
            if len(subtree_costs) < 3:
                coin[node] = 0
            else:
                # Get the three largest costs
                largest_costs = heapq.nlargest(3, subtree_costs)
                product = largest_costs[0] * largest_costs[1] * largest_costs[2]
                coin[node] = max(0, product)

        # Return size of subtree and costs
        return subtree_size, subtree_costs + [cost[node]]

    # Start DFS from the root node
    dfs(0)
    return coin
← Back to All Questions