Time Needed to Inform All Employees
MedPrompt
A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.
Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.
The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.
The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).
Return the number of minutes needed to inform all the employees about the urgent news.
Example 1:
Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.Example 2:
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.
Constraints:
1 <= n <= 1050 <= headID < nmanager.length == n0 <= manager[i] < nmanager[headID] == -1informTime.length == n0 <= informTime[i] <= 1000informTime[i] == 0if employeeihas no subordinates.- It is guaranteed that all the employees can be informed.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach calculates the time required for the news to reach each individual employee and then finds the maximum among them. For every employee, it traverses up the hierarchy to the head of the company, summing the informTime of each manager along the path.
Algorithm
- Initialize a variable
maxTimeto 0. - Iterate through each employee
ifrom0ton-1. - For each employee, calculate the time it takes for the news to reach them by traversing up the management chain.
- Initialize
pathTime = 0andcurrentEmployee = i. - While
currentEmployeehas a manager (i.e.,manager[currentEmployee] != -1):- Move up to the manager:
currentEmployee = manager[currentEmployee]. - Add the manager's
informTimeto thepathTime:pathTime += informTime[currentEmployee].
- Move up to the manager:
- Initialize
- After the inner loop,
pathTimeholds the total time for the news to reach the initial employeei. - Update the overall maximum time:
maxTime = Math.max(maxTime, pathTime). - After iterating through all employees, return
maxTime.
Walkthrough
The core idea is that the time for an employee i to be informed is the sum of the informTime of all their managers up to the company head. We can iterate through each employee from 0 to n-1. For each employee i, we start a loop that moves from i to manager[i], then to manager[manager[i]], and so on, until we reach the head (manager[...]==-1). In this loop, we accumulate the informTime of the managers. We keep a global variable, maxTime, to store the maximum time calculated across all employees. After checking all employees, maxTime will hold the result. This method is simple to understand but inefficient because it repeatedly calculates the time for the upper parts of the management tree. For example, if employees A and B have the same manager M, the path from M to the head is calculated twice.
class Solution { public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { int maxTime = 0; for (int i = 0; i < n; i++) { int currentTime = 0; int currentEmployee = i; // Traverse up the management chain while (manager[currentEmployee] != -1) { currentEmployee = manager[currentEmployee]; currentTime += informTime[currentEmployee]; } maxTime = Math.max(maxTime, currentTime); } return maxTime; }}Complexity
Time
O(N * H), where N is the number of employees and H is the height of the management tree. In the worst case of a skewed tree (like a linked list), H can be O(N), leading to a time complexity of O(N^2).
Space
O(1) extra space. We only use a few variables to track the current employee and time during the traversal, not counting the input arrays.
Trade-offs
Pros
Simple to conceptualize and implement.
Very low memory overhead, using O(1) extra space.
Cons
Highly inefficient for deep or skewed trees, leading to a worst-case time complexity of O(N^2).
Performs many redundant calculations. The time for a manager's branch to be informed is recalculated for each of their subordinates.
Solutions
Solution
public class Solution { private List < int > [] g; private int[] informTime; public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) { g = new List < int > [n]; for (int i = 0; i < n; ++i) { g[i] = new List < int > (); } this.informTime = informTime; for (int i = 0; i < n; ++i) { if (manager[i] != -1) { g[manager[i]].Add(i); } } return dfs(headID); } private int dfs(int i) { int ans = 0; foreach(int j in g[i]) { ans = Math.Max(ans, dfs(j) + informTime[i]); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.