Untitled

 avatar
unknown
plain_text
2 months ago
1.3 kB
9
Indexable
class Node:
    def __init__(self, number):
        self.number = number
        self.children = []
    def add_child(self, node):
        self.children.append(node)



class Solution:
    def find_least_quietest(self, node, quiet, least_quiet):
        least_quietest_number = node.number
        # Cache trick!!
        if node.number < len(least_quiet):
            return least_quiet[node.number] 
        for child in node.children:
            child_quiet_number = self.find_least_quietest(child, quiet, least_quiet)
            if quiet[child_quiet_number] < quiet[least_quietest_number]:
                least_quietest_number = child_quiet_number
        return least_quietest_number


    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        numbered_nodes = [Node(i) for i in range(n)]
        print("Creating numbered nodes")
        for richer_item in richer:
            _richer = numbered_nodes[richer_item[0]]
            _poorer = numbered_nodes[richer_item[1]]
            _poorer.add_child(_richer)
        least_quiet = []
        for i in range(n):
            print(f"Finding least quietest for {i}")
            least_quiet.append(self.find_least_quietest(numbered_nodes[i], quiet, least_quiet))
        return least_quiet
        

Editor is loading...
Leave a Comment