Skip to main content
Talentd

Maximum Points After Collecting Coins From All Nodes - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationTree30 min readAsked at: De Shaw
Practice this problem

Problem Statement

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. 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 array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

  • Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
  • Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

 

Example 1:

Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11                        
Explanation: 
Collect all the coins from node 0 using the first way. Total points = 10 - 5 = 5.
Collect all the coins from node 1 using the first way. Total points = 5 + (10 - 5) = 10.
Collect all the coins from node 2 using the second way so coins left at node 3 will be floor(3 / 2) = 1. Total points = 10 + floor(3 / 2) = 11.
Collect all the coins from node 3 using the second way. Total points = 11 + floor(1 / 2) = 11.
It can be shown that the maximum points we can get after collecting coins from all the nodes is 11.

Example 2:

Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation: 
Coins will be collected from all the nodes using the first way. Therefore, total points = (8 - 0) + (4 - 0) + (4 - 0) = 16.

 

Constraints:

  • n == coins.length
  • 2 <= n <= 105
  • 0 <= coins[i] <= 104
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 104

Approach Overview

Problem Overview: You are given a tree where each node contains some coins. Starting from the root, you collect coins while traversing the tree, but each node forces a choice: take the coins now with a penalty k, or halve the coin value for the current node and all nodes in its subtree. The goal is to maximize the total points collected after visiting every node.

This structure immediately points to tree traversal combined with state tracking. Each decision affects the entire subtree, so the algorithm must remember how many times the coin value has been halved along the path from the root.

Approach 1: DFS with Subtree Points Calculation (O(n * k) time, O(n * k) space)

Traverse the tree using Depth-First Search. The key state is (node, shift), where shift represents how many times the coin values have been halved so far. For each node, compute two options: collect the current coin value after applying shift reductions and subtract k, or apply another reduction using a bit shift (coins[node] >> (shift + 1)) and propagate the increased reduction level to children. Recursively evaluate both choices for each child and accumulate the best result. Memoization avoids recomputing states because the same node and reduction level can appear through different paths. The number of reduction states is small (about 14 since coin values shrink quickly), which keeps the DFS efficient.

This approach works well because the tree has no cycles and each decision only affects the subtree. Bit shifting efficiently models repeated halving, making the calculation constant time per state.

Approach 2: Dynamic Programming on Trees (O(n * k) time, O(n * k) space)

This version explicitly models the problem as Dynamic Programming on a tree. Define dp[node][shift] as the maximum points obtainable from the subtree rooted at node when the coin value has been halved shift times. During DFS, compute results for children first, then evaluate the two choices at the current node: take coins now or apply another halving. For the "take" option, add (coins[node] >> shift) - k plus the best values from children with the same shift. For the "halve" option, use (coins[node] >> (shift + 1)) and combine with children evaluated at shift + 1. Store the maximum in the DP table.

This formulation makes the transition logic explicit and easier to reason about in interviews. The DP table ensures each (node, shift) state is computed once, giving linear complexity relative to the number of nodes multiplied by the limited number of reduction states.

Recommended for interviews: Tree DP with memoized DFS. Interviewers expect you to recognize that subtree decisions require passing state down the recursion. Starting with the DFS state definition shows understanding of tree traversal, while optimizing with memoization demonstrates strong dynamic programming skills.

Approach 1: DFS with Subtree Points Calculation

This approach leverages Depth-First Search (DFS) to traverse the tree and calculate the maximum possible points from collecting coins. We perform a DFS starting from the root node (0) and for each node, decide whether to collect its coins using the first or second method. The first method subtracts k from the node's coin value, whereas the second reduces all subtree nodes' coins by half. The key is to recursively calculate and choose the best option for every node.

The C solution involves organizing the graph structure using adjacency lists. The DFS function explores each node, calculating potential points for both ways of collecting coins (subtracting k or halving the subtree's coins). By comparing results, it ensures the maximum points are achieved.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) since we visit each node once.
Space Complexity: O(n) to store adjacency list and recursion stack.

Try this approach in the editor ā†’

Approach 2: Dynamic Programming on Trees

This approach uses dynamic programming to solve the problem on trees, known as DP on trees. We maintain a dp array to store the maximum points that can be collected from each subtree starting from a node. The transition relations help in deciding whether a node should be included without penalties or adjusted by halving the subtree values.

The C code outlines the skeleton where DP on trees is applied to compute potential points efficiently. By transforming each edge into transitions in the dp table, it evaluates maximal paths recursively and optimizes score calculation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), typical for tree dynamic programming where each node contributes.
Space Complexity: O(n) for storing intermediate dp results.

Try this approach in the editor ā†’

Approach 3: Memoization Search

First, we construct a graph g based on the edges given in the problem, where g[i] represents all adjacent nodes of node i. Then we can use the method of memoization search to solve this problem.

We design a function dfs(i, fa, j), which represents that the current node is i, the parent node is fa, the number of gold coins of the current node needs to be shifted to the right by j bits, and the maximum score that can be obtained.

The execution process of the function dfs(i, fa, j) is as follows:

If we use the first method to collect the gold coins of the current node, then the score of the current node is (coins[i] >> j) - k. Then we traverse all the adjacent nodes c of the current node. If c is not equal to fa, then we add the result of dfs(c, i, j) to the score of the current node.

If we use the second method to collect the gold coins of the current node, then the score of the current node is coins[i] >> (j + 1). Then we traverse all the adjacent nodes c of the current node. If c is not equal to fa, then we add the result of dfs(c, i, j + 1) to the score of the current node. Note that since the maximum value of coins[i] given in the problem is 10^4, we can only shift to the right by at most 14 bits, so that the value of coins[i] >> (j + 1) is 0.

Finally, we return the maximum score that can be obtained by using the two methods at the current node.

In order to avoid repeated calculations, we use the method of memoization search and store the result of dfs(i, fa, j) in f[i][j], where f[i][j] represents that the current node is i, the parent node is fa, the number of gold coins of the current node needs to be shifted to the right by j bits, and the maximum score that can be obtained.

The time complexity is O(n times log M), and the space complexity is O(n times log M). Where M represents the maximum value of coins[i].

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
DFS with Subtree Points Calculation

Time Complexity: O(n) since we visit each node once.
Space Complexity: O(n) to store adjacency list and recursion stack.

Dynamic Programming on Trees

Time Complexity: O(n), typical for tree dynamic programming where each node contributes.
Space Complexity: O(n) for storing intermediate dp results.

Memoization Searchā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Subtree Points CalculationO(n * k)O(n * k)General solution using recursion and memoization; easiest to implement
Dynamic Programming on TreesO(n * k)O(n * k)Best for interviews when you want a clear DP state definition

Video Solution

Maximum Points After Collecting Coins From All Nodes | Memoization | Optimisations | Leetcode - 2920 ā€¢ codestorywithMIK ā€¢ 4,331 views views

Watch 7 more video solutions ā†’

Frequently Asked Questions

Is Maximum Points After Collecting Coins From All Nodes easy or hard?
Maximum Points After Collecting Coins From All Nodes is classified as a Hard problem. It combines multiple advanced concepts including tree traversal, dynamic programming states, and bit manipulation, which makes the reasoning more complex than standard DFS problems.
Maximum Points After Collecting Coins From All Nodes Python/Java solution
Python, Java, and C++ implementations typically use DFS with memoization. A function dfs(node, parent, shift) computes the best score from that subtree. Results are cached in a DP structure to avoid recomputation, giving O(n * k) performance.
How to solve Maximum Points After Collecting Coins From All Nodes in O(n)?
A strict O(n) solution is not typical because each node must be evaluated across multiple reduction states. However, since the number of halving operations is bounded by about log2(maxCoin), the effective complexity becomes O(n * k) with k ā‰ˆ 14, which behaves close to linear in practice.
What is the best approach for Maximum Points After Collecting Coins From All Nodes?
The most effective approach is tree dynamic programming with memoized DFS. Each state is defined by (node, number of coin halvings applied so far). For every node you evaluate two choices: collect coins with penalty k or halve the value for the subtree. Memoizing results keeps the complexity around O(n * k), where k is the maximum number of reductions (about 14).
Is Maximum Points After Collecting Coins From All Nodes asked at Google/Amazon/Meta?
Tree dynamic programming problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving subtree decisions, state propagation during DFS, and maximizing scores on trees are common interview patterns.
What data structure is used in Maximum Points After Collecting Coins From All Nodes?
The problem primarily uses a tree represented with an adjacency list. The algorithm combines Depth-First Search traversal with dynamic programming states and bit manipulation (right shift) to simulate repeated coin halving efficiently.
What is the time complexity of Maximum Points After Collecting Coins From All Nodes?
The optimal solutions run in O(n * k) time, where n is the number of nodes in the tree and k is the number of possible coin reductions. Since each halving quickly reduces the value, k is small (roughly log of the maximum coin value). Space complexity is also O(n * k) due to memoization or DP storage.

Ready to solve this problem?

Practice Maximum Points After Collecting Coins From All Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays