DSA problem
Employee Importance
You have a data structure of employee information, including the employee's unique ID, their importance value, and their direct subordinates' IDs. You are given an array of employees employees where employees[i] is an Employee object with three fields (id, importance, subordinates), and a target employee's id. Return the total importance value of this employee and all of their direct and indirect subordinates.
The relationships among employees form a tree (or forest), but the input encodes them implicitly via subordinate-ID lists and an unordered employees array. A direct lookup by ID is O(n), so first build a hashmap from ID to Employee for O(1) access. After that the problem reduces to a standard tree-sum: starting from the target ID, return the importance of that employee plus the recursive total importance of each subordinate.
Because the underlying structure is acyclic by problem definition (subordinate relationships form a hierarchy), we do not need a visited set. A simple recursive DFS naturally accumulates the answer as it returns from each subtree.
Time is O(n) — every employee is visited at most once after the hashmap is built. Space is O(n) for the hashmap plus O(d) recursion stack where d is the tree depth (bounded by n).
Examples
employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 111employees = [[1,2,[5]],[5,-3,[]]], id = 5-3employees = [[1,1,[2]],[2,1,[3]],[3,1,[]]], id = 13Constraints
- 1 <= employees.length <= 2000
- 1 <= employees[i].id <= 2000
- All employees[i].id are unique.
- -100 <= employees[i].importance <= 100
- One employee has at most one direct leader and may have several subordinates.
- The IDs in employees[i].subordinates are valid IDs.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.