Find Number of Coins to Place in Tree Nodes

Find Number of Coins to Place in Tree Nodes - Problem

Dynamic Programming Tree Depth-First Search Sorting Heap (Priority Queue) Hard

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 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.

Input & Output

Example 1 — Basic Tree

$ Input: edges = [[0,1],[1,2],[1,3]], cost = [1,3,2,5]

› Output: [30,30,1,1]

💡 Note: Node 0 subtree {0,1,2,3} has max product 3×2×5=30. Node 1 subtree {1,2,3} has max product 3×2×5=30. Nodes 2,3 have subtree size <3, so get 1 coin each.

Example 2 — Negative Values

$ Input: edges = [[0,1],[0,2]], cost = [-2,3,-1]

› Output: [6,1,1]

💡 Note: Node 0 subtree {0,1,2} has costs [-2,3,-1]. Max product is (-2)×3×(-1)=6. Nodes 1,2 have subtree size 1, so get 1 coin each.

Example 3 — Single Node

$ Input: edges = [], cost = [5]

› Output: [1]

💡 Note: Only one node with subtree size 1 < 3, so it gets 1 coin.

Constraints

1 ≤ n ≤ 2 × 10⁴
edges.length == n - 1
0 ≤ a_i, b_i < n
-10⁴ ≤ cost[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree structure with cost values on each node

Subtree Analysis

For each node, analyze its subtree to determine coin placement

Coin Placement

Place coins based on subtree size and maximum product

Key Takeaway

🎯 Key Insight: Use DFS to collect subtree costs, then sort to efficiently find maximum product of any 3 values

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to use DFS to traverse the tree and collect subtree costs, then sort them to efficiently find the maximum product of 3 distinct values. For subtrees with <3 nodes, place 1 coin; otherwise find max product and place 0 if negative. Best approach uses DFS with sorted selection - Time: O(n² log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Sorted Selection	O(n² log n)	O(n)	Use DFS to traverse tree and sort costs to efficiently find maximum product
Brute Force with All Combinations	O(n⁴)	O(n²)	For each node, try all possible combinations of 3 nodes in its subtree

DFS with Sorted Selection — Algorithm Steps

Step 1: Build adjacency list and perform DFS to collect subtree costs for each node
Step 2: Sort costs in each subtree to identify largest positive and smallest negative values
Step 3: Try key combinations: 3 largest, 2 smallest negatives + 1 largest, etc.

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Costs

Use DFS to gather all costs in subtree

Sort Values

Sort costs to identify largest/smallest efficiently

Smart Selection

Try key combinations based on sorted order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void dfs(int node, int parent, int** adj, int* adjSize, int* cost, int* subtreeCosts, int* subtreeCostsSize) {
    subtreeCosts[(*subtreeCostsSize)++] = cost[node];
    for (int i = 0; i < adjSize[node]; i++) {
        int child = adj[node][i];
        if (child != parent) {
            dfs(child, node, adj, adjSize, cost, subtreeCosts, subtreeCostsSize);
        }
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long getMaxProduct(int* costs, int size) {
    if (size < 3) return 1;
    
    qsort(costs, size, sizeof(int), compare);
    
    long long maxProduct = LLONG_MIN;
    
    // Case 1: Three largest
    long long product1 = (long long)costs[size-1] * costs[size-2] * costs[size-3];
    if (product1 > maxProduct) maxProduct = product1;
    
    // Case 2: Two smallest and largest
    long long product2 = (long long)costs[0] * costs[1] * costs[size-1];
    if (product2 > maxProduct) maxProduct = product2;
    
    // Case 3: Smallest and two largest
    long long product3 = (long long)costs[0] * costs[size-1] * costs[size-2];
    if (product3 > maxProduct) maxProduct = product3;
    
    return maxProduct < 0 ? 0 : maxProduct;
}

int* solution(int** edges, int edgesSize, int* edgesColSize, int* cost, int costSize, int* returnSize) {
    int n = costSize;
    *returnSize = n;
    int* result = (int*)malloc(n * sizeof(int));
    
    if (n == 1) {
        result[0] = 1;
        return result;
    }
    
    // Build adjacency list
    int** adj = (int**)malloc(n * sizeof(int*));
    int* adjSize = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        adj[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0], b = edges[i][1];
        adj[a][adjSize[a]++] = b;
        adj[b][adjSize[b]++] = a;
    }
    
    for (int i = 0; i < n; i++) {
        int* subtreeCosts = (int*)malloc(n * sizeof(int));
        int subtreeCostsSize = 0;
        dfs(i, -1, adj, adjSize, cost, subtreeCosts, &subtreeCostsSize);
        result[i] = (int)getMaxProduct(subtreeCosts, subtreeCostsSize);
        free(subtreeCosts);
    }
    
    // Cleanup
    for (int i = 0; i < n; i++) {
        free(adj[i]);
    }
    free(adj);
    free(adjSize);
    
    return result;
}

int main() {
    // Simplified example
    int n = 4;
    int** edges = (int**)malloc(3 * sizeof(int*));
    for (int i = 0; i < 3; i++) {
        edges[i] = (int*)malloc(2 * sizeof(int));
    }
    
    edges[0][0] = 0; edges[0][1] = 1;
    edges[1][0] = 1; edges[1][1] = 2;
    edges[2][0] = 1; edges[2][1] = 3;
    
    int cost[] = {1, 3, 2, 5};
    int returnSize;
    int* result = solution(edges, 3, NULL, cost, 4, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

For each of n nodes, collect subtree costs O(n) and sort them O(n log n)

⚠ Quadratic Growth

Space Complexity

O(n)

Store adjacency list and temporary arrays for subtree costs

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Sorted Selection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler