Approach #1: Depth-First Search [Accepted]

Intuition and Algorithm

Let's use a hashmap emap = { -> employee} to query employees quickly.

Now to find the total importance of an employee, it will be the importance of that employee, plus the total importance of each of that employee's subordinates. This is a straightforward depth-first search.

Complexity Analysis

  • Time Complexity: , where is the number of employees. We might query each employee in dfs.

  • Space Complexity: , the size of the implicit call stack when evaluating dfs.

Analysis written by: @awice.