Problem statement

https://leetcode.com/problems/loud-and-rich/

Solution

Consider the directed graph with edge x -> y if y is richer than x. Then for each person x, we want the quietest person in the subtree at x. Idea is to use dfs with post-order traversal: given node first found answers for all children and find the quietest candidate among answers for children and node itself.

Complexity

It is O(m) for time and space where m = len(richer).

Code

```python class Solution: def loudAndRich(self, richer, quiet): n = len(quiet) G = defaultdict(list) for u, v in richer: G[v].append(u)

    ans = {}
    def dfs(node):
        if node not in ans:
            ans[node] = min([dfs(child) for child in G[node]] + [node], key = lambda x: quiet[x])
        return ans[node]
    
    return [dfs(i) for i in range(n)] ``