Maximum Points After Collecting Coins From All Nodes Solution
Maximum Points After Collecting Coins From All Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Points After Collecting Coins From All Nodes is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Depth-First Search, Trees, Bit Manipulation
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0. You are given edges, where edges[i] = [a, b] is an edge, an array coins where node i holds coins[i] coins, and an integer k.
Coins must be collected from every node, and a node can only be collected after its parent has been. When you collect node i you choose one of two ways:
- Take
coins[i] - kpoints. This may be negative. - Take
floor(coins[i] / 2)points — and every node ini's subtree then has its coin count halved (rounded down) as well.
Halvings stack: a node under two nodes that chose the second way has been halved twice by the time it is collected.
Return the maximum total points you can get.
Example 1
Input: edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
Output: 11
Explanation: Take 10 - 5 = 5 at node 0 and at node 1. At node 2 take floor(3 / 2) = 1, which halves node 3 to 1; take floor(1 / 2) = 0 there. Total 11.
Example 2
Input: edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
Output: 16
Explanation: With k = 0 the first way always gives the full count: 8 + 4 + 4.
Example 3
Input: edges = [[1,0]], coins = [0,7], k = 3
Output: 1
Explanation: Either take 0 - 3 = -3 at the root and then 7 - 3 = 4 at node 1, or take floor(0 / 2) = 0 at the root — which halves node 1 to 3 — and then floor(3 / 2) = 1. Both total 1.
Constraints
n == coins.length2 <= n <= 10^50 <= coins[i] <= 10^4edges.length == n - 10 <= edges[i][0], edges[i][1] < n0 <= k <= 10^4The edges form a tree
Hints for Maximum Points After Collecting Coins From All Nodes
Hint 1
What does a node need to know about its ancestors' choices? Only how many of them chose the halving way.
Hint 2
Coins are at most
10^4 < 2^14, so after 14 halvings every count is 0 — the halving count can be capped at 14.Hint 3
Let
f(u, h)be the best score inu's subtree when its coins have been halvedhtimes:max((coins[u] >> h) - k + Σ f(child, h), (coins[u] >> (h + 1)) + Σ f(child, min(h + 1, 14))).
How to solve Maximum Points After Collecting Coins From All Nodes
A node's options depend only on how many ancestors halved — and that number stops mattering after 14, since every coin count is below 2^14. That gives a tree DP with 15 states per node.
Approach
- Build the adjacency list and an order in which parents come before children (BFS from 0), remembering each node's parent.
- Process nodes in reverse order. Keep
S[u][h], the sum off(child, h)overu's children processed so far. - For each
hfrom 0 to 14:f(u, h) = max((coins[u] >> h) - k + S[u][h], (coins[u] >> (h + 1)) + S[u][min(h + 1, 14)]). - Add
f(u, ·)intoS[parent(u)]. The answer isf(0, 0).
Why it works
Halving h times and then rounding down equals a right shift by h, so a node's coins under h ancestor halvings are coins[u] >> h. The two choices at u affect its subtree only through h (unchanged or plus one), so subtrees of different children are independent given h, which is exactly what the DP sums. Capping at 14 is exact because x >> 14 = 0 for every allowed coin count.
Complexity
- Time —
O(n · 15) - Space —
O(n · 15)
Pitfalls
- Without the cap,
hcould grow to the depth of the tree and the table would beO(n^2). - The first way can be negative — the best score for a subtree is not simply the sum of positive choices.
- A deep path tree overflows the call stack in recursive solutions; process nodes iteratively.
Reference solution
Python
from typing import List
def maximumPoints(edges: List[List[int]], coins: List[int], k: int) -> int:
n = len(coins)
H = 15 # coins < 2^14, so 14 halvings already reach 0
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent = [-1] * n
order = [0]
seen = [False] * n
seen[0] = True
i = 0
while i < len(order):
u = order[i]
i += 1
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
order.append(v)
S = [[0] * H for _ in range(n)]
root = 0
for u in reversed(order):
c = coins[u]
su = S[u]
fu = [0] * H
for h in range(H):
a = (c >> h) - k + su[h]
b = (c >> (h + 1)) + su[min(h + 1, H - 1)]
fu[h] = a if a > b else b
p = parent[u]
if p >= 0:
sp = S[p]
for h in range(H):
sp[h] += fu[h]
else:
root = fu[0]
return rootJava
public static int maximumPoints(int[][] edges, int[] coins, int k) {
int n = coins.length, H = 15; // coins < 2^14, so 14 halvings already reach 0
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] parent = new int[n], order = new int[n];
boolean[] seen = new boolean[n];
Arrays.fill(parent, -1);
int tail = 0;
order[tail++] = 0;
seen[0] = true;
for (int q = 0; q < tail; q++) {
int u = order[q];
for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; order[tail++] = v; }
}
long[][] S = new long[n][H];
long[] fu = new long[H];
long root = 0;
for (int q = n - 1; q >= 0; q--) {
int u = order[q], c = coins[u];
for (int h = 0; h < H; h++) {
long a = (c >> h) - k + S[u][h];
long b = (c >> (h + 1)) + S[u][Math.min(h + 1, H - 1)];
fu[h] = Math.max(a, b);
}
if (parent[u] >= 0) for (int h = 0; h < H; h++) S[parent[u]][h] += fu[h];
else root = fu[0];
}
return (int) root;
}C++
int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
int n = coins.size();
const int H = 15; // coins < 2^14, so 14 halvings already reach 0
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> parent(n, -1), order;
vector<bool> seen(n, false);
order.push_back(0);
seen[0] = true;
for (int q = 0; q < (int) order.size(); q++) {
int u = order[q];
for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; order.push_back(v); }
}
vector<vector<long long>> S(n, vector<long long>(H, 0));
long long fu[H];
long long root = 0;
for (int q = n - 1; q >= 0; q--) {
int u = order[q], c = coins[u];
for (int h = 0; h < H; h++) {
long long a = (c >> h) - k + S[u][h];
long long b = (c >> (h + 1)) + S[u][min(h + 1, H - 1)];
fu[h] = max(a, b);
}
if (parent[u] >= 0) for (int h = 0; h < H; h++) S[parent[u]][h] += fu[h];
else root = fu[0];
}
return (int) root;
}JavaScript
var maximumPoints = function(edges, coins, k) {
var n = coins.length, H = 15; // coins < 2^14, so 14 halvings already reach 0
var adj = [];
for (var i = 0; i < n; i++) adj.push([]);
for (var i = 0; i < edges.length; i++) {
adj[edges[i][0]].push(edges[i][1]);
adj[edges[i][1]].push(edges[i][0]);
}
var parent = new Array(n).fill(-1), seen = new Array(n).fill(false), order = [0];
seen[0] = true;
for (var q = 0; q < order.length; q++) {
var u = order[q];
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (!seen[v]) { seen[v] = true; parent[v] = u; order.push(v); }
}
}
var S = new Array(n * H).fill(0), root = 0, fu = new Array(H);
for (var q = n - 1; q >= 0; q--) {
var u = order[q], c = coins[u];
for (var h = 0; h < H; h++) {
var a = (c >> h) - k + S[u * H + h];
var b = (c >> (h + 1)) + S[u * H + Math.min(h + 1, H - 1)];
fu[h] = a > b ? a : b;
}
if (parent[u] >= 0) {
for (var h = 0; h < H; h++) S[parent[u] * H + h] += fu[h];
} else {
root = fu[0];
}
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming