Employee Importance - Solution & Explanation

Problem Overview: You’re given a list of employees where each employee has an id, an importance value, and a list of direct subordinates. The task is to compute the total importance for a given employee, including the importance of all direct and indirect subordinates in the hierarchy.

The structure naturally forms a management tree. Each employee points to their children (subordinates). The main challenge is quickly locating employees by ID and traversing the hierarchy without repeatedly scanning the entire array.

Approach 1: Depth-First Search (DFS) using Recursion (Time: O(n), Space: O(n))

First build a hash map that maps employee id to the corresponding employee object. This allows constant-time lookup when you need to find a subordinate. Starting from the target employee ID, perform a recursive depth-first search through all subordinates. For each employee visited, add their importance and recursively process each subordinate ID.

The key insight: every employee is visited exactly once. The recursion naturally follows the management hierarchy, which behaves like a tree. Time complexity is O(n) because each employee is processed once. Space complexity is O(n) due to the hash map and recursion stack in the worst case. This approach directly applies concepts from Depth-First Search and Hash Table usage.

Approach 2: Breadth-First Search (BFS) using Queue (Time: O(n), Space: O(n))

The same preprocessing step applies: build a map from employee ID to employee object. Instead of recursion, use a queue to perform a breadth-first traversal of the hierarchy. Start by pushing the target employee ID into the queue. While the queue is not empty, pop an employee, add their importance to the total, and push all their subordinates into the queue.

This approach processes employees level by level in the management hierarchy. Each employee still gets visited exactly once, so the time complexity remains O(n). The queue can hold up to all employees in the worst case, giving O(n) space complexity. BFS is often preferred if you want to avoid recursion depth issues or when working iteratively. It demonstrates standard Breadth-First Search traversal on a tree-like hierarchy.

Recommended for interviews: Both DFS and BFS solutions are optimal with O(n) time. Interviewers typically expect the DFS solution because it maps directly to the recursive structure of the hierarchy. Showing the hash map optimization is critical; without it, repeated scans of the employee list would degrade performance. Implementing either DFS or BFS cleanly demonstrates strong understanding of graph/tree traversal.