FIND NUMBER OF COINS TO PLACE IN BINARY TREE NODES | LEETCODE 2973 | PYTHON DFS + HEAP SOLUTION

Channel Discord Community: / discord
Problem Link: leetcode.com/problems/find-nu...
Today we are solving probably one of the most horrendous problems I've ever seen... asked by the anti-hero of coding interviews known exclusively for asking this kind of absolute nonsense (Google)... It's Leetcode 2973: Find Number of Coins to Place in Binary Tree Nodes. This question is just too much...
TIMESTAMPS
00:00
00:10 Question Prompt
01:20 Basic Example
04:35 Solution Intuition
08:00 Coding
21:40 Time/Space Complexity
24:10 Outro

[@crackfaang]

Code since it's hard to see it all:
class Solution:
def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
self.graph = collections.defaultdict(list)
self.cost = cost
for edge1, edge2 in edges:
self.graph[edge1].append(edge2)
self.graph[edge2].append(edge1)
self.visited = set()
self.res = [0] * len(cost)
self.dfs(0)
return self.res
def dfs(self, node):
self.visited.add(node)
node_count = 1
largest = [self.cost[node]]
negatives = []
if self.cost[node] < 0:
negatives = [-self.cost[node]]
for edge in self.graph[node]:
if edge not in self.visited:
edge_count, edge_largest, edge_negatives = self.dfs(edge)
node_count += edge_count
for val in edge_largest:
heapq.heappush(largest, val)
if len(largest) > 3:
heapq.heappop(largest)
for val in edge_negatives:
heapq.heappush(negatives, val)
if len(negatives) > 2:
heapq.heappop(negatives)
if node_count < 3:
self.res[node] = 1
else:
product = 1
for val in largest:
product *= val
res = product
if len(negatives) == 2:
negatives_product = negatives[0] * negatives[1]
res = max(
res,
negatives_product * max(largest)
)
if res < 0:
self.res[node] = 0
else:
self.res[node] = res
return node_count, largest, negatives

[@stutiagrawal9643]

The way you explain, really makes this problem easier. Thank you !!

[@GunalanDeivaganpathy]

i dont get why we make bidirectional , as we are only seeing sub tree nodes tho

[@GunalanDeivaganpathy]

very good explanation

[@pinkpastry1365]

My friend was asked the same question in his google interview.