[C++, Java, Python] DFS | Track 3 Positive Max 2 Negative Min | Modular Code
Intuition\n\nTo calculate coins for current node curr, what information do we need?\n- Number of nodes in the subtree rooted at curr, so that we can decide if w
# Intuition\n\nTo calculate coins for current node `curr`, what information do we need?\n- Number of nodes in the subtree rooted at `curr`, so that we can decide if we need to place 1 coin or not.\n- Something to calculate maximum product of 3 cost values in that subtree.\n  - If all costs were positive, then we would have needed maximum 3 values in that, because they will give maximum product.\n  - But, here we have negative costs too. Suppose we had subtree costs as `[-100, -50, 1, 30, 5]`, then maximum product would have been $-100\\times -50\\times 30$.\n  - So, we need 3 positive maximum, and 2 negative minimum.\n\n# Approach\n\nAll this can be stored in a class `X` as:\n\n```C++ []\nclass X {\npublic:\n    // number of nodes in subtree\n    int numNodes;\n    // posMax: [maximum, second maximum, third maximum]\n    // negMin: [minimum, second minimum]\n    vector<int> posMax, negMin;\n\n    // default constructor\n    X() : numNodes(0) {}\n\n    // constructor with one cost value (or one tree node)\n    X(int val) {\n        numNodes = 1;\n        if (val > 0) {\n            posMax.push_back(val);\n        }\n        else {\n            negMin.push_back(val);\n        }\n    }\n};\n```\n```Java []\nclass X {\n    // number of nodes in subtree\n    public int numNodes;\n    // posMax: [maximum, second maximum, third maximum]\n    // negMin: [minimum, second minimum]\n    public ArrayList<Integer> posMax, negMin;\n\n    // default constructor\n    public X() {\n        numNodes = 0;\n        posMax = new ArrayList<>();\n        negMin = new ArrayList<>();\n    }\n\n    // constructor with one cost value (or one tree node)\n    public X(int val) {\n        numNodes = 1;\n        posMax = new ArrayList<>();\n        negMin = new ArrayList<>();\n        if (val > 0) {\n            posMax.add(val);\n        } else {\n            negMin.add(val);\n        }\n    }\n}\n```\n```Python []\nclass X:\n    def __init__(self, val: int):\n        \'\'\'constructor with one cost value (or one tree node)\'\'\'\n        \n        # number of nodes in subtree\n        self.numNodes = 1\n        \n        # posMax: [maximum, second maximum, third maximum]\n        # negMin: [minimum, second minimum]\n        self.posMax, self.negMin = [], []\n        self.posMax.append(val) if val > 0 else self.negMin.append(val)\n```\n\nNow, apply DFS on the given tree starting from root `0`, going down the tree.\n- Recursively call on all the children of current node. Here, we assume that these recursive calls will fill the `coins` array for complete subtree rooted at that child.\n- Every child returns their object of class `X`.\n- Update the information for current tree using that object.\n  - Update number of nodes, by adding the child\'s subtree nodes.\n  - Update 3 postive maximum and 2 negative minimum.\n\n```C++ []\n// update current node with child\'s information\nvoid update(X x) {\n    // add child\'s nodes\n    numNodes += x.numNodes;\n\n    // add child\'s maximum(s) and minimum(s)\n    posMax.insert(posMax.end(), x.posMax.begin(), x.posMax.end());\n    negMin.insert(negMin.end(), x.negMin.begin(), x.negMin.end());\n\n    // sort them and select top 3 maximum and top 2 minimum\n    sort(posMax.begin(), posMax.end(), greater<int>());\n    sort(negMin.begin(), negMin.end());\n    posMax.resize(min((int)posMax.size(), 3));\n    negMin.resize(min((int)negMin.size(), 2));\n}\n```\n```Java []\n// update current node with child\'s information\npublic void update(X x) {\n    // add child\'s nodes\n    numNodes += x.numNodes;\n\n    // add child\'s maximum(s) and minimum(s)\n    posMax.addAll(x.posMax);\n    negMin.addAll(x.negMin);\n\n    // sort them and select top 3 maximum and top 2 minimum\n    posMax.sort(Collections.reverseOrder());\n    negMin.sort(null);\n    while (posMax.size() > 3) {\n        posMax.remove(posMax.size() - 1);\n    }\n    while (negMin.size() > 2) {\n        negMin.remove(negMin.size() - 1);\n    }\n}\n```\n```Python []\ndef update(self, x: X):\n    \'\'\'update current node with child\'s information\'\'\'\n    \n    # add child\'s nodes\n    self.numNodes += x.numNodes\n    \n    # add child\'s maximum(s) and minimum(s)\n    # sort them and select top 3 maximum and top 2 minimum\n    self.posMax = sorted(self.posMax + x.posMax, reverse=True)[:3]\n    self.negMin = sorted(self.negMin + x.negMin)[:2]\n```\n\nTo calculate the maximum product, we only need 3 positive maximum and 2 negative minimum. We have two choices for maximum product:\n- `posMax[0] * posMax[1] * posMax[2]`\n- `negMin[0] * negMin[1] * posMax[0]`\n\n```C++ []\n// maximum product of subtree\nlong long product() {\n    // case 1\n    if (numNodes < 3) {\n        return 1;\n    }\n    // case 2\n    long long result = 0;\n    // choice 1 (all positive)\n    if (posMax.size() == 3) {\n        result = 1LL * posMax[0] * posMax[1] * posMax[2];\n    }\n    // choice 2 (2 negative 1 positive)\n    if (negMin.size() == 2 && !posMax.empty()) {\n        result = max(result, 1LL * negMin[0] * negMin[1] * posMax[0]);\n    }\n    return result;\n}\n```\n```Java []\n// maximum product of subtree\npublic long product() {\n    // case 1\n    if (numNodes < 3) {\n        return 1;\n    }\n    // case 2\n    long result = 0;\n    // choice 1 (all positive)\n    if (posMax.size() == 3) {\n        result = (long)posMax.get(0) * posMax.get(1) * posMax.get(2);\n    }\n    // choice 2 (2 negative 1 positive)\n    if (negMin.size() == 2 && !posMax.isEmpty()) {\n        result = Math.max(result, (long)negMin.get(0) * negMin.get(1) * posMax.get(0));\n    }\n    return result;\n}\n```\n```Python []\ndef product(self) -> int:\n    \'\'\'maximum product of subtree\'\'\'\n    \n    # case 1\n    if self.numNodes < 3:\n        return 1\n    # case 2\n    result = 0\n    # choice 1 (all positive)\n    if len(self.posMax) == 3:\n        result = self.posMax[0] * self.posMax[1] * self.posMax[2]\n    # choice 2 (2 negative 1 positive)\n    if len(self.negMin) == 2 and self.posMax:\n        result = max(result, self.negMin[0] * self.negMin[1] * self.posMax[0])\n    return result\n```\n\n# Code\n\n```C++ []\nclass X {\npublic:\n    // number of nodes in subtree\n    int numNodes;\n    // posMax: [maximum, second maximum, third maximum]\n    // negMin: [minimum, second minimum]\n    vector<int> posMax, negMin;\n\n    // default constructor\n    X() : numNodes(0) {}\n\n    // constructor with one cost value (or one tree node)\n    X(int val) {\n        numNodes = 1;\n        if (val > 0) {\n            posMax.push_back(val);\n        }\n        else {\n            negMin.push_back(val);\n        }\n    }\n\n    // update current node with child\'s information\n    void update(X x) {\n        // add child\'s nodes\n        numNodes += x.numNodes;\n\n        // add child\'s maximum(s) and minimum(s)\n        posMax.insert(posMax.end(), x.posMax.begin(), x.posMax.end());\n        negMin.insert(negMin.end(), x.negMin.begin(), x.negMin.end());\n\n        // sort them and select top 3 maximum and top 2 minimum\n        sort(posMax.begin(), posMax.end(), greater<int>());\n        sort(negMin.begin(), negMin.end());\n        posMax.resize(min((int)posMax.size(), 3));\n        negMin.resize(min((int)negMin.size(), 2));\n    }\n\n    // maximum product of subtree\n    long long product() {\n        // case 1\n        if (numNodes < 3) {\n            return 1;\n        }\n        // case 2\n        long long result = 0;\n        // choice 1 (all positive)\n        if (posMax.size() == 3) {\n            result = 1LL * posMax[0] * posMax[1] * posMax[2];\n        }\n        // choice 2 (2 negative 1 positive)\n        if (negMin.size() == 2 && !posMax.empty()) {\n            result = max(result, 1LL * negMin[0] * negMin[1] * posMax[0]);\n        }\n        return result;\n    }\n};\n\nclass Solution {\nprivate:\n    // Depth-First Search on tree\n    // fills coins array\n    X fillCoins(int n, vector<vector<int>>& graph, vector<int>& cost, int curr, int prev, vector<long long>& coins) {\n        // maintain information of current subtree\n        X x(cost[curr]);\n        for (int next : graph[curr]) {\n            // avoid calling function back to parent\n            if (next != prev) {\n                // fillCoins() returns information of child\'s subtree\n                // update current subtree with child\'s information\n                x.update(fillCoins(n, graph, cost, next, curr, coins));\n            }\n        }\n        // once information of current subtree is completed\n        // calculate maximum product\n        coins[curr] = x.product();\n        // return information to parent\n        return x;\n    }\n\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        // make tree in adjacency list form\n        vector<vector<int>> graph(n);\n        for (auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n            graph[edge[1]].push_back(edge[0]);\n        }\n        vector<long long> coins(n);\n        // call DFS and fill coins array\n        fillCoins(n, graph, cost, 0, -1, coins);\n        return coins;\n    }\n};\n```\n```Java []\nclass X {\n    // number of nodes in subtree\n    public int numNodes;\n    // posMax: [maximum, second maximum, third maximum]\n    // negMin: [minimum, second minimum]\n    public ArrayList<Integer> posMax, negMin;\n\n    // default constructor\n    public X() {\n        numNodes = 0;\n        posMax = new ArrayList<>();\n        negMin = new ArrayList<>();\n    }\n\n    // constructor with one cost value (or one tree node)\n    public X(int val) {\n        numNodes = 1;\n        posMax = new ArrayList<>();\n        negMin = new ArrayList<>();\n        if (val > 0) {\n            posMax.add(val);\n        } else {\n            negMin.add(val);\n        }\n    }\n\n    // update current node with child\'s information\n    public void update(X x) {\n        // add child\'s nodes\n        numNodes += x.numNodes;\n\n        // add child\'s maximum(s) and minimum(s)\n        posMax.addAll(x.posMax);\n        negMin.addAll(x.negMin);\n\n        // sort them and select top 3 maximum and top 2 minimum\n        posMax.sort(Collections.reverseOrder());\n        negMin.sort(null);\n        while (posMax.size() > 3) {\n            posMax.remove(posMax.size() - 1);\n        }\n        while (negMin.size() > 2) {\n            negMin.remove(negMin.size() - 1);\n        }\n    }\n\n    // maximum product of subtree\n    public long product() {\n        // case 1\n        if (numNodes < 3) {\n            return 1;\n        }\n        // case 2\n        long result = 0;\n        // choice 1 (all positive)\n        if (posMax.size() == 3) {\n            result = (long)posMax.get(0) * posMax.get(1) * posMax.get(2);\n        }\n        // choice 2 (2 negative 1 positive)\n        if (negMin.size() == 2 && !posMax.isEmpty()) {\n            result = Math.max(result, (long)negMin.get(0) * negMin.get(1) * posMax.get(0));\n        }\n        return result;\n    }\n}\n\nclass Solution {\n    // Depth-First Search on tree\n    // fills coins array\n    X fillCoins(int n, ArrayList<ArrayList<Integer>> graph, int[] cost, int curr, int prev, long[] coins) {\n        // maintain information of current subtree\n        X x = new X(cost[curr]);\n        for (int next : graph.get(curr)) {\n            // avoid calling function back to parent\n            if (next != prev) {\n                // fillCoins() returns information of child\'s subtree\n                // update current subtree with child\'s information\n                x.update(fillCoins(n, graph, cost, next, curr, coins));\n            }\n        }\n        // once information of current subtree is completed\n        // calculate maximum product\n        coins[curr] = x.product();\n        return x;\n    }\n\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        int n = cost.length;\n        // make tree in adjacency list form\n        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            graph.add(new ArrayList<>());\n        }\n        for (int[] edge : edges) {\n            graph.get(edge[0]).add(edge[1]);\n            graph.get(edge[1]).add(edge[0]);\n        }\n        long[] coins = new long[n];\n        // call DFS and fill coins array\n        fillCoins(n, graph, cost, 0, -1, coins);\n        return coins;\n    }\n}\n```\n```Python []\nclass X:\n    def __init__(self, val: int):\n        \'\'\'constructor with one cost value (or one tree node)\'\'\'\n        \n        # number of nodes in subtree\n        self.numNodes = 1\n        \n        # posMax: [maximum, second maximum, third maximum]\n        # negMin: [minimum, second minimum]\n        self.posMax, self.negMin = [], []\n        self.posMax.append(val) if val > 0 else self.negMin.append(val)\n    \n    def update(self, x: X):\n        \'\'\'update current node with child\'s information\'\'\'\n        \n        # add child\'s nodes\n        self.numNodes += x.numNodes\n        \n        # add child\'s maximum(s) and minimum(s)\n        # sort them and select top 3 maximum and top 2 minimum\n        self.posMax = sorted(self.posMax + x.posMax, reverse=True)[:3]\n        self.negMin = sorted(self.negMin + x.negMin)[:2]\n    \n    def product(self) -> int:\n        \'\'\'maximum product of subtree\'\'\'\n        \n        # case 1\n        if self.numNodes < 3:\n            return 1\n        # case 2\n        result = 0\n        # choice 1 (all positive)\n        if len(self.posMax) == 3:\n            result = self.posMax[0] * self.posMax[1] * self.posMax[2]\n        # choice 2 (2 negative 1 positive)\n        if len(self.negMin) == 2 and self.posMax:\n            result = max(result, self.negMin[0] * self.negMin[1] * self.posMax[0])\n        return result\n\n\nclass Solution:\n    def fillCoins(self, graph: List[List[int]], cost: List[int], curr: int, prev: int, coins: List[int]) -> X:\n        \'\'\'\n        Depth-First Search on tree\n        fills coins array\n        \'\'\'\n        \n        # maintain information of current subtree\n        x = X(cost[curr])\n        for next in graph[curr]:\n            # avoid calling function back to parent\n            if next != prev:\n                # fillCoins() returns information of child\'s subtree\n                # update current subtree with child\'s information\n                x.update(self.fillCoins(graph, cost, next, curr, coins))\n        \n        # once information of current subtree is completed\n        # calculate maximum product\n        coins[curr] = x.product()\n        \n        # return information to parent\n        return x\n    \n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        n = len(cost)\n        # make tree in adjacency list form\n        graph = [[] for _ in range(n)]\n        for edge in edges:\n            graph[edge[0]].append(edge[1])\n            graph[edge[1]].append(edge[0])\n        coins = [0] * n\n        # call DFS and fill coins array\n        self.fillCoins(graph, cost, 0, -1, coins)\n        return coins\n```\n\n# Complexity\n\n## Time Complexity: $O(n)$\n\n**Class X**\n\n- `constructor(s)`: $O(1)$\n- `update()`: `posMax` has atmost 3 values and `negMin` has atmost 2 values. Adding two of them will make atmost 6 and 4 values respectively. Sorting them will be $O(6 \\log 6)$ and $O(4 \\log 4)$ respectively. Hence, the function is $O(1)$.\n- `product()`: $O(1)$\n\n**Class Solution**\n\n- `fillCoins(root)` visits all $n$ nodes once. In one call, it recursively calls on all child nodes and update information of current node. It has time complexity of $O(V+E)$ in graph terminology. For tree, $V=n$ and $E=n-1$.\n- `placedCoins()` makes tree in $O(E)$ time.\n\n## Space Complexity: $O(n)$\n\n- Tree in adjacency list form takes $O(V+E)$ space.\n- DFS recursion stack space is $O(V)$ (for skewed tree).\n
['Depth-First Search', 'Design', 'C++', 'Java', 'Python3']