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].id is the ID of the ith employee.employees[i].importance is the importance value of the ith employee.employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee.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 <= 2000employees[i].id are unique.-100 <= employees[i].importance <= 100employees[i].subordinates are valid IDs.The problem can be approached by using a Depth-First Search (DFS). The main idea is to accumulate the importance of an employee and all of their direct and indirect subordinates. We use a recursive function to traverse the subordinates of each employee. The base case is when an employee has no subordinates (leaf node). Each recursion step accumulates importance from the current employee and proceeds to accumulate from its subordinates.
This Python solution defines a recursive dfs function that fetches an employee from a map (created for fast lookup) and calculates their total importance including their subordinates recursively.
C++
Java
C#
JavaScript
Time Complexity: O(N), where N is the number of employees, as each employee is visited once.
Space Complexity: O(N), due to the recursion stack and storage in the map for employees.
An alternative method involves using Breadth-First Search (BFS). In this approach, a queue is used to iteratively explore each level of employee hierarchy starting from the given employee ID. One processes each employee by summing their importance and enqueuing their subordinates. This technique assures visiting all employees in a breadth-wise manner and eventually collecting the cumulative importance value.
This Python code uses a BFS approach. We employ a queue where we enqueue employees as we visit them and total their importance. Every dequeued employee adds their importance to the result and their subordinates to the queue.
C++
Java
C#
JavaScript
Time Complexity: O(N), as it processes each employee once.
Space Complexity: O(N), due to the queue and employee mapping storage.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) using Recursion | Time Complexity: O(N), where N is the number of employees, as each employee is visited once. |
| Breadth-First Search (BFS) using Queue | Time Complexity: O(N), as it processes each employee once. |
employee importance | employee importance leetcode | tree bfs | leetcode 690 • Naresh Gupta • 2,551 views views
Watch 9 more video solutions →Practice Employee Importance with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor