Approach #1: Cached DepthFirst Search [Accepted]
Intuition
Consider the directed graph with edge x > y
if y
is richer than x
.
For each person x
, we want the quietest person in the subtree at x
.
Algorithm
Construct the graph described above, and say dfs(person)
is the quietest person in the subtree at person
. Notice because the statements are logically consistent, the graph must be a DAG  a directed graph with no cycles.
Now dfs(person)
is either person
, or min(dfs(child) for child in person)
. That is to say, the quietest person in the subtree is either the person
itself, or the quietest person in some subtree of a child of person
.
We can cache values of dfs(person)
as answer[person]
, when performing our postorder traversal of the graph. That way, we don't repeat work. This technique reduces a quadratic time algorithm down to linear time.
Complexity Analysis

Time Complexity: , where is the number of people.

Space Complexity: , the space used by the
answer
, and the implicit call stack ofdfs
.
Analysis written by: @awice.