Employee Importance
Problem Description
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 the ith employee.employees[i].importanceis the importance value of the ith employee.employees[i].subordinatesis 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 <= 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.
Solve it on LeetCode
Approaches
1. Depth-First Search (DFS) Recursion
Intuition:
The main idea is to recursively calculate the total importance by summing up the importance of the given employee and recursively adding the importance of all subordinates. We will use a hashmap to quickly access an employee using their id.
Approach:
- Use a hashmap to store the employee id and the related
Employeeobject for quick retrieval. - Write a recursive helper function
dfsthat takes the id of the employee whose total importance is to be calculated. - The
dfsfunction will retrieve the employee using the hashmap, start the sum with the employee's importance, and recursively add the importance of all subordinates by callingdfsfor each subordinate id. - Call the
dfsfunction starting with the given employee id.
Code:
- Time Complexity:
O(N), whereNis the number of employees. We visit each employee once. - Space Complexity:
O(N), due to the recursion stack in the worst case and the space used by the hashmap.
2. Breadth-First Search (BFS)
Intuition:
Instead of using recursion, we can implement an iterative version using a queue, which will help us traverse through the employees in a level-order approach (breadth-first search).
Approach:
- Similar to DFS, use a hashmap to store employees by their id for quick access.
- Use a queue to help in the BFS approach, starting by adding the main employee id to the queue.
- While the queue is not empty, get the next id, add its importance, and add all its subordinates to the queue.
- Continue summing up the importance until the queue is empty and return the total importance.
Code:
- Time Complexity:
O(N), whereNis the number of employees. We visit each employee once. - Space Complexity:
O(N), due to the space used by the hashmap and the queue.