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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
Dictionary<int, List<int>> subordinateMap = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
if (!subordinateMap.ContainsKey(manager[i])) {
subordinateMap[manager[i]] = new List<int>();
}
subordinateMap[manager[i]].Add(i);
}
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((headID, 0));
int maxTime = 0;
while (queue.Count > 0) {
var (current, time) = queue.Dequeue();
maxTime = Math.Max(maxTime, time);
if (subordinateMap.ContainsKey(current)) {
foreach (var sub in subordinateMap[current]) {
queue.Enqueue((sub, time + informTime[current]));
}
}
}
return maxTime;
}
}The C# solution uses a queue to implement the BFS traversal. Each element in the queue represents an employee and the total time taken to inform this employee. The function iteratively processes the employees until all are informed.