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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Number of Coins to Place in Tree Nodes

Number: 3218

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n-1) rooted at node 0, an array edges represents the tree structure and a 0-indexed array cost assigns an integer cost to each node. For every node, you must place coins on it based on its subtree:

  • If the size of the subtree (node itself and all its descendants) is less than 3, place 1 coin.
  • Otherwise, compute the maximum possible product of cost values from any 3 distinct nodes in that subtree. However, if the maximum computed product is negative, place 0 coins. Return an array coin where coin[i] is the number of coins placed at node i.

Key Insights

  • Use Depth-First Search (DFS) from the root to process each node’s subtree.
  • At each node, we need to calculate two types of candidate values from the entire subtree:
    • The top three maximum cost values (to compute candidate1 = abc).
    • The bottom two (i.e. the smallest) cost values (to compute candidate2 = smallest1 * smallest2 * largest).
  • The answer for a node with subtree size at least 3 is the larger of candidate1 and candidate2, with a final check to return 0 if the maximum product is negative.
  • Only tracking the top three maximum and bottom two minimum values in each subtree is sufficient to determine the maximum product without storing all node cost values.
  • The DFS returns an aggregator (top 3 maximum list, bottom 2 minimum list, and subtree count) that helps merge results from child subtrees efficiently.

Space and Time Complexity

Time Complexity: O(n) since for each node we perform a constant amount of work (merging fixed-size lists). Space Complexity: O(n) due to the recursion call stack and the auxiliary data structures maintained for each node.

Solution

We perform a DFS starting from the root. For each node:

  1. Initialize aggregator with the node’s cost (both as the only member for maximum and minimum lists) and count = 1.
  2. For each child (avoiding the parent to prevent cycles), recursively obtain the aggregator (top three maximum, bottom two minimum, and count) and merge it with the current node’s aggregator.
  3. Merging simply involves taking the union of the current lists with the child’s lists and then selecting the top three maximum elements (by descending order) and the bottom two minimum elements (by ascending order).
  4. Once the entire subtree is processed, if the subtree count is less than 3, assign coin = 1. Otherwise, compute:
    • candidate1 as the product of the top three maximum values.
    • candidate2 as the product of the two smallest cost values and the largest maximum value.
    • The coin value at this node is max(candidate1, candidate2) if it is nonnegative; otherwise, assign 0.
  5. Return the computed aggregator for parent's merging.

This approach leverages the fact that only a fixed number of candidates (3 maximum values and 2 minimum values) are needed to compute the desired product.

Code Solutions

# Python solution with detailed comments

def findCoins(edges, cost):
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(30000)  # Increase recursion limit as n can be large

    n = len(cost)
    tree = defaultdict(list)
    # Build an undirected tree
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
        
    # Result array to hold coin count for each node
    coins = [0] * n
    
    # DFS function returns a tuple: (max_list, min_list, count)
    # max_list: top 3 maximum cost values in this subtree (sorted descending)
    # min_list: bottom 2 minimum cost values in this subtree (sorted ascending)
    # count: total number of nodes in this subtree
    def dfs(node, parent):
        # Initialize aggregator for current node with its cost value
        max_list = [cost[node]]
        min_list = [cost[node]]
        count = 1
        
        # Process all children (neighbors not equal to parent)
        for child in tree[node]:
            if child == parent:
                continue
            c_max, c_min, c_count = dfs(child, node)
            count += c_count
            # Merge current max_list with child's max_list
            merged_max = max_list + c_max
            # Sort descending and keep top 3 elements
            merged_max.sort(reverse=True)
            max_list = merged_max[:3]
            
            # Merge current min_list with child's min_list
            merged_min = min_list + c_min
            # Sort ascending and keep first 2 (smallest) elements
            merged_min.sort()
            min_list = merged_min[:2]
        
        # Compute coin value for current node based on its subtree size
        if count < 3:
            coins[node] = 1
        else:
            candidate1 = None
            candidate2 = None
            if len(max_list) >= 3:
                candidate1 = max_list[0] * max_list[1] * max_list[2]
            if len(min_list) >= 2 and len(max_list) >= 1:
                candidate2 = min_list[0] * min_list[1] * max_list[0]
            # Choose maximum among the candidates (if one is None, use the other)
            candidate = candidate1 if candidate2 is None else candidate2 if candidate1 is None else max(candidate1, candidate2)
            # If candidate is negative, assign 0 coins
            coins[node] = candidate if candidate >= 0 else 0
        
        # Return the aggregator
        return max_list, min_list, count
    
    dfs(0, -1)
    return coins

# Example usage:
#print(findCoins([[0,1],[0,2],[0,3],[0,4],[0,5]], [1,2,3,4,5,6]))
← Back to All Questions