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.
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.