Sponsored
Sponsored
We can think of the employee-manager structure as a tree. The head of the company is the root, and each employee is a node whose parent is the manager. Our goal is to determine the maximum time required to inform all employees. We can perform a Depth-First Search (DFS) starting from the headID to explore all paths and calculate the time required for each path.
Time Complexity: O(n). Each node is visited exactly once.
Space Complexity: O(n). The recursion stack can go up to the depth of the tree, which in the worst case can be n.
1def numOfMinutes(n, headID, manager, informTime):
2 from collections import defaultdict
3
4 subordinate_map = defaultdict(list)
5 for emp, man in enumerate(manager):
6 subordinate_map[man].append(emp)
7
8 def dfs(emp_id):
9 max_time = 0
10 for sub in subordinate_map[emp_id]:
11 max_time = max(max_time, dfs(sub))
12 return informTime[emp_id] + max_time
13
14 return dfs(headID)The solution employs a Depth-First Search (DFS) starting from the headID. The recursive DFS function calculates the maximum time required by iterating through all the subordinates.
We use a Breadth-First Search (BFS) approach to explore the company hierarchy level by level. We maintain a queue to propagate the information and calculate the total time as we move through each level of subordinates.
Time Complexity: O(n) because each employee is processed exactly once.
Space Complexity: O(n) due to the space required to store the subordinate map and the queue.
1function numOfMinutes(n, headID, manager, informTime) {
The JavaScript solution employs a BFS to explore the hierarchy using a queue. It calculates the total time taken to inform every employee by processing them level by level.