Approach #1: Cached Depth-First 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 post-order 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 of dfs.


Analysis written by: @awice.