Greedy | Maintaining Largest Three and Smallest Two for each Sub-Tree | Easy Explanation
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- Product of two -ve numbers is +ve.\n- Smallest two numbers may also generate la
![image.png](https://assets.leetcode.com/users/images/68853048-6a1e-46a0-8951-b716b60cf4b2_1703430869.313049.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Product of two -ve numbers is +ve.\n- Smallest two numbers may also generate larger value on multiplication (as compared to largest two values), therefore, we should keep track of them as well. \nEx : \n    - (-10) X (-9) = 90\n    - 1 X 2 = 2 . \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Do post-order traversal of tree.\n- At each step, \nMaintain largest 3 cost values for that tree *(We are going to use pq2 for that)*, smallest 2 cost values *(We are going to use pq_smallest2 for that).*\n- Also, at each step, update both priority-queues for parent as well \n*(We are going to use pq1, pq_smallest1 for parent).*\n- Find both possible products and get the maximum among them for the currNode.\n    - If, current subtree has less than three nodes, then, \n        $$maxProduct[currNode]$$ $$=$$ $$1$$.\n    - Else if, maximum product (among the two products calculated above) is -ve, then, \n        $$maxProduct[currNode]$$ $$=$$ $$0$$.\n    - Else, \n        $$maxProduct[currNode]$$ $$=$$ $$maximum$$ $$among$$ $$the$$ $$two$$ $$products$$ $$(calculated$$ $$above)$$.\n\n# Complexity\n- Time complexity: $$O(N)$$\n    - *At each step, we are doing simple tree traversal and checking/updating a priority-queue of size 3 (at max).*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n    - *We are maintaining two arrays of size $$N$$.*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    void updateMinHeap(priority_queue<long long int, vector<long long int>, greater<long long int> >&pq2, long long int value){\n        if(pq2.size() < 3){\n            pq2.push(value);\n        }\n        else{\n            if(pq2.top() < value){\n                pq2.pop();\n                pq2.push(value);\n            }\n        }\n        return;\n    }\n\n    void updateMaxHeap(priority_queue<long long int>&pq_smallest2, long long int value){\n        if(pq_smallest2.size() < 2){\n            pq_smallest2.push(value);\n        }\n        else{\n            if(pq_smallest2.top() > value){\n                pq_smallest2.pop();\n                \n                pq_smallest2.push(value);\n            }\n        }\n        return;\n    }\n\n    void fillMaxThreeNodesProduct(long long int currNode, long long int parentNode, priority_queue<long long int, vector<long long int>, greater<long long int> >&pq1, priority_queue<long long int>&pq_smallest1, vector<vector<long long int>>&children, vector<long long int>&maxProduct, vector<int>&cost){\n        \n        priority_queue<long long int, vector<long long int>, greater<long long int> >pq2;\n        priority_queue<long long int>pq_smallest2;\n        \n        // do postorder traversal\n        for(auto child : children[currNode]){\n            if(child != parentNode){\n                fillMaxThreeNodesProduct(child, currNode, pq2, pq_smallest2, children, maxProduct, cost);\n            }\n        }\n        // then update currNode in both priority queues\n        updateMinHeap(pq2, cost[currNode]);\n        updateMaxHeap(pq_smallest2, cost[currNode]);\n\n        long long int elementsInPQ2 = pq2.size();\n\n        // process product1 of curr subtree\n        long long int currProduct = 1, product1 = 1, product2 = 1, largestElement = INT_MIN;\n        while(!pq2.empty()){\n            product1 = product1 * pq2.top();\n            largestElement = max(largestElement, pq2.top());\n            \n            long long int value = pq2.top();   \n            pq2.pop();\n\n            updateMinHeap(pq1, value);\n        }\n\n        // process product2 of curr subtree\n        while(!pq_smallest2.empty()){\n            long long int value = pq_smallest2.top();\n\n            product2 = product2 * value; \n            pq_smallest2.pop();\n\n            updateMaxHeap(pq_smallest1, value);\n        }\n        product2 = product2 * largestElement;\n        \n        // check conditions\n        if(elementsInPQ2 < 3){\n            maxProduct[currNode] = 1;\n        }\n        else{   \n            currProduct = max(product1, product2);\n            maxProduct[currNode] = max((long long int)0, currProduct);\n        }\n        \n        return;\n    }\n \n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        long long int n = edges.size() + 1;\n        vector<vector<long long int>>children(n);\n        for(int i = 0; i < edges.size(); ++i){\n            children[edges[i][0]].push_back(edges[i][1]);\n            children[edges[i][1]].push_back(edges[i][0]);\n        }\n        \n        priority_queue<long long int, vector<long long int>, greater<long long int> >pq;\n        priority_queue<long long int>pq_smallest;\n        vector<long long int>maxProduct(n);\n        fillMaxThreeNodesProduct(0, -1, pq, pq_smallest, children, maxProduct, cost);\n        \n        return maxProduct;\n    }\n};\n```
['Math', 'Greedy', 'Tree', 'Heap (Priority Queue)', 'C++']