Employee Importance
Understanding the Problem
We are given a flat list of employees, each with an ID, an importance value, and a list of their direct subordinate IDs. Given a target employee ID, we need to compute the total importance of that employee plus every employee underneath them in the hierarchy, no matter how many levels deep.
The employee structure forms a tree (or more precisely, a forest, but we only care about the subtree rooted at the target). The complication is that employees arrive as a flat list, not as linked tree nodes. A subordinate is referenced only by ID, so before we can move from an employee to their subordinates, we need a way to resolve any ID to its employee object.
The problem therefore has two parts: build a fast lookup from employee ID to employee object, then traverse the subtree rooted at the target employee, accumulating importance values along the way.
Key Constraints:
1 <= employees.length <= 2000-> Even rescanning the list for every ID lookup, O(n^2) overall, would pass at this size, but a hash map gives O(n) for the same amount of code.-100 <= importance <= 100-> Importance values are small. Even summing all 2000 employees at their maximum gives 2000 * 100 = 200,000, well within 32-bit integer range. No overflow concerns here.- No cycles in subordination -> The structure is a tree, so we do not need cycle detection or a visited set during traversal.
idis guaranteed valid -> No need to handle "employee not found" errors.
Approach 1: DFS (Recursive)
Intuition
The total importance of an employee equals their own importance plus the total importance of each of their direct subordinates. That definition is already recursive: each subordinate's total is computed the same way, and the recursion bottoms out at employees with no subordinates.
Before we can traverse, we need a way to jump from a subordinate ID to the actual employee object. The input gives us a list, and scanning it for every lookup would cost O(n) each time. So we first build a hash map from employee ID to employee object. After that, the DFS is short: look up the target, add their importance, recurse on each subordinate ID.
Each employee has at most one direct leader, so any ID appears in at most one subordinates list. There is exactly one path from the target down to each employee in their subtree, which means the recursion visits each of those employees once, with no visited set needed. The no-cycles guarantee ensures the recursion terminates.
Algorithm
- Build a hash map that maps each employee's ID to their employee object.
- Define a recursive function
dfs(id)that: - Looks up the employee in the map.
- Starts with this employee's importance value.
- For each subordinate ID, recursively calls
dfsand adds the returned value. - Returns the total.
- Call
dfswith the given target ID and return the result.
Example Walkthrough
Trace employees = [[1, 5, [2, 3]], [2, 3, [4]], [3, 4, []], [4, 1, []]] with id = 1. Employee 4 is an indirect subordinate of employee 1, reachable only through employee 2, so the recursion has to go two levels deep on that branch.
Code
- Time Complexity: O(n). Building the hash map takes O(n). The DFS visits each employee in the target's subtree at most once, doing O(1) work per visit. Total subordinate edges processed across all visits is at most n - 1.
- Space Complexity: O(n). The hash map stores all n employees. The recursion call stack goes as deep as the height of the subtree, which in the worst case (a chain) is O(n).
Recursive DFS is optimal in time, but it spends call-stack space proportional to the depth of the hierarchy, and a long management chain can overflow the stack. The next approach replaces the implicit call stack with an explicit queue.
Approach 2: BFS (Iterative)
Intuition
Instead of recursing into subordinates, we can use a queue to process employees iteratively. Start by adding the target employee's ID to the queue. Then, while the queue is not empty, dequeue an ID, look up the employee, add their importance to a running total, and enqueue all their subordinate IDs. This explores the entire subtree without any risk of stack overflow.
BFS and DFS visit the same set of employees in a different order. BFS processes the target first, then all direct subordinates, then all employees two levels down, and so on. The total importance ends up the same regardless of traversal order because addition is commutative.
Algorithm
- Build a hash map that maps each employee's ID to their employee object.
- Initialize a queue with the target employee's ID.
- Initialize a total importance counter to 0.
- While the queue is not empty:
- Dequeue an employee ID.
- Look up the employee in the map.
- Add their importance to the total.
- Enqueue all their subordinate IDs.
- Return the total.
Example Walkthrough
The same input as before: employees = [[1, 5, [2, 3]], [2, 3, [4]], [3, 4, []], [4, 1, []]] with id = 1. BFS reaches employee 3 before employee 4, the reverse of the DFS order, and still arrives at the same total of 13.
Code
- Time Complexity: O(n). Building the hash map is O(n). The BFS visits each employee in the target's subtree once, doing O(1) work per employee. Total subordinate IDs enqueued across all visits is at most n - 1.
- Space Complexity: O(n). The hash map stores all n employees. The queue holds at most O(n) employee IDs in the worst case (a very wide tree where the target has all others as direct subordinates).