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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
6 List<List<Integer>> subordinateMap = new ArrayList<>(n);
7 for (int i = 0; i < n; i++) {
8 subordinateMap.add(new ArrayList<>());
9 }
10 for (int emp = 0; emp < n; emp++) {
11 if (manager[emp] != -1) {
12 subordinateMap.get(manager[emp]).add(emp);
13 }
14 }
15
16 return dfs(headID, informTime, subordinateMap);
17 }
18
19 private int dfs(int empId, int[] informTime, List<List<Integer>> subordinateMap) {
20 int max = 0;
21 for (int subId : subordinateMap.get(empId)) {
22 max = Math.max(max, dfs(subId, informTime, subordinateMap));
23 }
24 return informTime[empId] + max;
25 }
26}The Java solution also uses DFS to explore the hierarchy tree. We maintain a list of lists to store all subordinates for every manager and recursively calculate the required time.
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.