Approach #1: Cached Depth-First Search [Accepted]
Consider the directed graph with edge
x -> y if
y is richer than
For each person
x, we want the quietest person in the subtree at
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.
dfs(person) is either
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
We can cache values of
answer[person], when performing our post-order traversal of the graph. That way, we don't repeat work. This technique reduces a quadratic time algorithm down to linear time.
Time Complexity: , where is the number of people.
Space Complexity: , the space used by the
answer, and the implicit call stack of
Analysis written by: @awice.