Employee Importance
Last Updated: March 28, 2026
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 catch is that employees are given as a list, not as a tree data structure. We cannot directly jump from an employee to their subordinates by following pointers. We need a way to look up any employee by their ID.
So the problem really has two parts. First, build a fast lookup from employee ID to employee object. Second, traverse the subtree rooted at the target employee, accumulating importance values along the way. This is a classic graph/tree traversal problem disguised in a real-world wrapper.
Key Constraints:
1 <= employees.length <= 2000-> With at most 2000 employees, even an O(n^2) solution would finish instantly. But O(n) is clean and straightforward, so there is no reason to settle for worse.-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 most natural way to think about this problem is recursively. The total importance of an employee equals their own importance plus the total importance of each of their direct subordinates. Each subordinate's total importance is defined the same way, recursively, expanding until we hit 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 through it every time would be wasteful. So we first build a hash map from employee ID to employee object. After that, the DFS is straightforward: look up the target, add their importance, recurse on each subordinate ID.
The employee hierarchy is a tree, and DFS naturally explores every node in a subtree. By starting at the target employee and recursing into each subordinate, we visit exactly the employees we need: the target plus all direct and indirect subordinates. The hash map ensures that jumping from a subordinate's ID to their employee object takes O(1) time, so the traversal is not bottlenecked by lookup overhead.
The recursion mirrors the problem's definition perfectly. "Total importance of employee X" equals "X's importance + total importance of each subordinate." This is textbook divide and conquer on a tree.
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
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).
The DFS approach is already optimal, but recursion uses the call stack. For very deep hierarchies, we could risk a stack overflow. What if we want an iterative solution that avoids the implicit call stack entirely?
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, just 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.
BFS explores all reachable nodes from a starting point by expanding outward level by level. Since the employee hierarchy is a tree (no cycles), every employee in the target's subtree is reachable and will be visited exactly once. The queue ensures we process every subordinate, and their subordinates, without missing anyone or double-counting.
The hash map is critical. Without it, every time we dequeue a subordinate ID, we would need to scan through the entire employee list to find the matching object. With the map, that lookup is O(1), keeping the overall traversal linear.
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
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).