Python | Short
Intuition\n\nBy exchange argument, the maximum product cannot involve numbers that are neither among the three smallest nor among the three largest.\n\n# Approa
# Intuition\n\nBy exchange argument, the maximum product cannot involve numbers that are neither among the three smallest nor among the three largest.\n\n# Approach\n\nOnce you found at most six said numbers, you can brute force all triplets because there are at most Binom(6, 3) = 20 of them.\n\n# Complexity\n\n- Time complexity: $$O(n \\log n)$$. Comes from `sorted` but you can replace it with `heapq.{nsmallest,nlargest}`.\n\n- Space complexity: $$O(n)$$.\n\n# Code\n```\nclass Solution:\n    def placedCoins(self, edges: list[list[int]], cost: list[int]) -> list[int]:\n        g = defaultdict(list)\n        for u, v in edges:\n            g[u].append(v)\n            g[v].append(u)\n\n        coin = [0] * len(cost)\n\n        def dfs(v, p):\n            subtree = [cost[v]] + list(chain.from_iterable(dfs(u, v) for u in g[v] if u != p))\n            candidates = sorted(subtree)[:3] + sorted(subtree)[3:][-3:]\n            coin[v] = max(0, max(map(prod, combinations(candidates, 3)), default=1))\n            return candidates\n\n        dfs(0, 0)\n        return coin\n\n```
['Depth-First Search', 'Sorting', 'Heap (Priority Queue)', 'Combinatorics', 'Python3']