Employee Importance

To solve this problem, we’ll perform a Depth-First Search (DFS) starting from the given employee ID, and recursively add the importance of all the subordinates.

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        # Create a dictionary for quick lookup
        emap = {e.id: e for e in employees}

        def dfs(eid):
            employee = emap[eid]
            return employee.importance + sum(dfs(eid) for eid in employee.subordinates)

        return dfs(id)

In this code:

  1. We first build a dictionary emap to map employee ID to the employee object. This allows us to quickly look up an employee by their ID.
  2. We define a helper function dfs to perform the Depth-First Search. For a given employee ID, this function returns the sum of the employee’s importance and the total importance of their subordinates.
  3. We call dfs with the given ID to start the search.

This solution works because it recursively explores all subordinates of each employee, adding up their importance values. The use of a dictionary allows quick lookups of employees, making the algorithm efficient.