Employee Importance - Video Solutions
花花酱 LeetCode 690. Employee Importance - 刷题找工作 EP75
Employee Importance - Video Solution
Watch 10 video solutions for Employee Importance, a medium level problem involving Array, Hash Table, Tree. This walkthrough by Hua Hua has 3,181 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.
You are given an array of employees employees where:
employees[i].idis the ID of theithemployee.employees[i].importanceis the importance value of theithemployee.employees[i].subordinatesis a list of the IDs of the direct subordinates of theithemployee.
Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.
Example 1:
Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1 Output: 11 Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3. They both have an importance value of 3. Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.
Example 2:
Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5 Output: -3 Explanation: Employee 5 has an importance value of -3 and has no direct subordinates. Thus, the total importance value of employee 5 is -3.
Constraints:
1 <= employees.length <= 20001 <= employees[i].id <= 2000- All
employees[i].idare unique. -100 <= employees[i].importance <= 100- One employee has at most one direct leader and may have several subordinates.
- The IDs in
employees[i].subordinatesare valid IDs.
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS using Recursion + Hash Map | O(n) | O(n) | Most common interview solution. Clean recursive traversal of the hierarchy. |
| BFS using Queue + Hash Map | O(n) | O(n) | Preferred when avoiding recursion or when iterative traversal is required. |