Maximum Points After Collecting Coins From All Nodes

Hard
1643.

Maximum Points After Collecting Coins From All Nodes

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.

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:

  1. Take coins[i] - k points. This may be negative.
  2. Take floor(coins[i] / 2) points — and every node in i'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.length
  • 2 <= n <= 10^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 10^4
  • The edges form a tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges
 * @param {number[]} coins
 * @param {number} k
 * @return {number}
 */
var maximumPoints = function(edges, coins, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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:

  1. Take coins[i] - k points. This may be negative.
  2. Take floor(coins[i] / 2) points — and every node in i'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.length
  • 2 <= n <= 10^5
  • 0 <= coins[i] <= 10^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 0 <= k <= 10^4
  • The edges form a tree

Hints for Maximum Points After Collecting Coins From All Nodes

  1. Hint 1

    What does a node need to know about its ancestors' choices? Only how many of them chose the halving way.

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

  3. Hint 3

    Let f(u, h) be the best score in u's subtree when its coins have been halved h times: 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

  1. Build the adjacency list and an order in which parents come before children (BFS from 0), remembering each node's parent.
  2. Process nodes in reverse order. Keep S[u][h], the sum of f(child, h) over u's children processed so far.
  3. For each h from 0 to 14: f(u, h) = max((coins[u] >> h) - k + S[u][h], (coins[u] >> (h + 1)) + S[u][min(h + 1, 14)]).
  4. Add f(u, ·) into S[parent(u)]. The answer is f(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, h could grow to the depth of the tree and the table would be O(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 root

Java

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