LeetCode 2920: Maximum Points After Collecting Coins From All Nodes Solution

Master LeetCode problem 2920 (Maximum Points After Collecting Coins From All Nodes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2920. Maximum Points After Collecting Coins From All Nodes

Hard

Array Dynamic Programming Bit Manipulation Tree Depth-First Search Memoization

Problem Explanation

Explanation

To solve this problem, we can use a depth-first search (DFS) approach on the tree starting from the root node. We will keep track of two values for each node:

The maximum points we can get from the subtree rooted at that node if we collect all coins from that node.
The maximum points we can get from the subtree rooted at that node if we leave some coins uncollected.

We will calculate these values for each node recursively using DFS. At each node, we have two choices:

Collect all coins and deduct k points.
Collect half of the coins and propagate the remaining coins to its children.

Finally, we return the maximum points that can be obtained starting from the root node.

Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(n) for the recursive stack.

Solution Code

class Solution {
    public int maxPoints(int[][] edges, int[] coins, int k) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
        }
        
        return dfs(0, -1, coins, k, graph)[0];
    }
    
    private int[] dfs(int node, int parent, int[] coins, int k, Map<Integer, List<Integer>> graph) {
        int maxPointsWithNode = Math.max(0, coins[node] - k);
        int maxPointsWithoutNode = 0;
        
        for (int child : graph.getOrDefault(node, new ArrayList<>())) {
            if (child == parent) continue;
            int[] childResult = dfs(child, node, coins, k, graph);
            maxPointsWithNode += childResult[1];
            maxPointsWithoutNode += Math.max(childResult[0], childResult[1]);
        }
        
        return new int[] {maxPointsWithNode, maxPointsWithoutNode};
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2920 (Maximum Points After Collecting Coins From All Nodes)?

This page provides optimized solutions for LeetCode problem 2920 (Maximum Points After Collecting Coins From All Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2920 (Maximum Points After Collecting Coins From All Nodes)?

The time complexity for LeetCode 2920 (Maximum Points After Collecting Coins From All Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2920 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2920 in Java, C++, or Python.

Back to LeetCode Solutions