2920. Maximum Points After Collecting Coins From All Nodes LeetCode Solution
In this guide, you will get 2920. Maximum Points After Collecting Coins From All Nodes LeetCode Solution with the best time and space complexity. The solution to Maximum Points After Collecting Coins From All Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Points After Collecting Coins From All Nodes
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
Complexity Analysis
Time Complexity: O(\log (10^4) \cdot n) = O(n)
Space Complexity: O(n)
2920. Maximum Points After Collecting Coins From All Nodes LeetCode Solution in C++
class Solution {
public:
int maximumPoints(vector<vector<int>>& edges, vector<int>& coins, int k) {
const int n = coins.size();
vector<vector<int>> graph(n);
vector<vector<int>> mem(n, vector<int>(kMaxHalved + 1, -1));
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
return dfs(graph, 0, /*prev=*/-1, coins, k, /*halved=*/0, mem);
}
private:
static constexpr int kMaxCoin = 10000;
static constexpr int kMaxHalved = 13; // log2(kMaxCoin) = 13
int dfs(const vector<vector<int>>& graph, int u, int prev,
const vector<int>& coins, int k, int halved,
vector<vector<int>>& mem) {
// All the children will be 0, so no need to explore.
if (halved > kMaxHalved)
return 0;
if (mem[u][halved] != -1)
return mem[u][halved];
const int val = coins[u] / (1 << halved);
int takeAll = val - k;
int takeHalf = floor(val / 2.0);
for (const int v : graph[u]) {
if (v == prev)
continue;
takeAll += dfs(graph, v, u, coins, k, halved, mem);
takeHalf += dfs(graph, v, u, coins, k, halved + 1, mem);
}
return mem[u][halved] = max(takeAll, takeHalf);
}
}; /* code provided by PROGIEZ */
2920. Maximum Points After Collecting Coins From All Nodes LeetCode Solution in Java
class Solution {
public int maximumPoints(int[][] edges, int[] coins, int k) {
final int n = coins.length;
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
Integer[][] mem = new Integer[n][kMaxHalved + 1];
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
return dfs(graph, 0, /*prev=*/-1, coins, k, /*halved=*/0, mem);
}
private static final int kMaxCoin = 10000;
private static final int kMaxHalved = (int) (Math.log(kMaxCoin) / Math.log(2)) + 1;
private int dfs(List<Integer>[] graph, int u, int prev, int[] coins, int k, int halved,
Integer[][] mem) {
// All the children will be 0, so no need to explore.
if (halved > kMaxHalved)
return 0;
if (mem[u][halved] != null)
return mem[u][halved];
final int val = coins[u] / (1 << halved);
int takeAll = val - k;
int takeHalf = (int) Math.floor(val / 2.0);
for (final int v : graph[u]) {
if (v == prev)
continue;
takeAll += dfs(graph, v, u, coins, k, halved, mem);
takeHalf += dfs(graph, v, u, coins, k, halved + 1, mem);
}
return mem[u][halved] = Math.max(takeAll, takeHalf);
}
} // code provided by PROGIEZ
2920. Maximum Points After Collecting Coins From All Nodes LeetCode Solution in Python
class Solution:
def maximumPoints(
self,
edges: list[list[int]],
coins: list[int],
k: int,
) -> int:
kMaxCoin = 10000
kMaxHalved = int(kMaxCoin).bit_length()
n = len(coins)
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
@functools.lru_cache(None)
def dfs(u: int, prev: int, halved: int) -> int:
# All the children will be 0, so no need to explore.
if halved > kMaxHalved:
return 0
val = coins[u] // (1 << halved)
takeAll = val - k
takeHalf = math.floor(val / 2)
for v in graph[u]:
if v == prev:
continue
takeAll += dfs(v, u, halved)
takeHalf += dfs(v, u, halved + 1)
return max(takeAll, takeHalf)
return dfs(0, -1, 0) # code by PROGIEZ
