Skip to content

690. Employee Importance

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int getImportance(vector<Employee*> employees, int id) {
    unordered_map<int, Employee*> idToEmployee;

    for (Employee* employee : employees)
      idToEmployee[employee->id] = employee;

    return dfs(id, idToEmployee);
  }

 private:
  int dfs(int id, const unordered_map<int, Employee*>& idToEmployee) {
    int values = 0;

    for (const int subId : idToEmployee.at(id)->subordinates)
      values += dfs(subId, idToEmployee);

    return idToEmployee.at(id)->importance + values;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int getImportance(List<Employee> employees, int id) {
    Map<Integer, Employee> idToEmployee = new HashMap<>();

    for (Employee employee : employees)
      idToEmployee.put(employee.id, employee);

    return dfs(id, idToEmployee);
  }

  private int dfs(int id, Map<Integer, Employee> idToEmployee) {
    int values = 0;

    for (final int subId : idToEmployee.get(id).subordinates)
      values += dfs(subId, idToEmployee);

    return idToEmployee.get(id).importance + values;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def getImportance(self, employees: list['Employee'], id: int) -> int:
    idToEmployee = {employee.id: employee for employee in employees}

    def dfs(id: int) -> int:
      values = idToEmployee[id].importance
      for subId in idToEmployee[id].subordinates:
        values += dfs(subId)
      return values

    return dfs(id)