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.
This approach models the problem as finding the longest path in a tree, where the path weight is defined by the informTime. It uses a Depth-First Search (DFS) starting from the head of the company. This is a much more efficient method as it avoids redundant calculations.
Algorithm
- First, build an adjacency list representation of the tree from the
managerarray. For each manager, the list will contain all their direct subordinates. - Define a recursive function,
dfs(managerID). - Base Case: If
managerIDhas no subordinates (a leaf node), return 0. - Recursive Step:
- Initialize
maxSubordinateTime = 0. - For each
subordinateofmanagerID:- Recursively call
dfs(subordinate)and updatemaxSubordinateTime = Math.max(maxSubordinateTime, dfs(subordinate)).
- Recursively call
- The total time for the subtree rooted at
managerIDisinformTime[managerID] + maxSubordinateTime. Return this value.
- Initialize
- The final answer is the result of calling
dfs(headID).
Walkthrough
First, we need to represent the company hierarchy as a tree. An adjacency list is a suitable data structure for this, where adj[i] stores a list of all direct subordinates of employee i. We can build this list by iterating through the manager array once. Then, we define a recursive DFS function, say dfs(managerID). This function will compute the time it takes for the news to propagate from managerID to all employees in their subtree. The base case for the recursion is an employee who has no subordinates (a leaf in the tree). For them, the time required is 0. For a manager u, the total time for their branch is their own informTime[u] plus the maximum time required for any of their direct subordinates' branches. The recursive step is: time(u) = informTime[u] + max(dfs(v)) for all subordinates v of u. We initiate the process by calling dfs(headID). This approach traverses each node and edge of the tree exactly once, making it very efficient.
import java.util.ArrayList;import java.util.List; class Solution { public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { List<List<Integer>> adj = new ArrayList<>(n); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { if (manager[i] != -1) { adj.get(manager[i]).add(i); } } return dfs(headID, adj, informTime); } private int dfs(int managerID, List<List<Integer>> adj, int[] informTime) { if (adj.get(managerID).isEmpty()) { return 0; } int maxSubordinateTime = 0; for (int subordinate : adj.get(managerID)) { maxSubordinateTime = Math.max(maxSubordinateTime, dfs(subordinate, adj, informTime)); } return informTime[managerID] + maxSubordinateTime; }}Complexity
Time
O(N). We visit each employee once to build the adjacency list (O(N)) and once during the DFS traversal (O(N)).
Space
O(N). The adjacency list requires O(N) space. The recursion stack for DFS can go up to a depth of H (the tree height), which is O(N) in the worst case of a skewed tree.
Trade-offs
Pros
Optimal time complexity of O(N).
Each employee (node) is processed only once, avoiding redundant work.
It's an intuitive mapping of the problem to a classic tree traversal algorithm.
Cons
Requires O(N) extra space to store the adjacency list.
Deep recursion on a skewed tree could potentially lead to a
StackOverflowErrorfor extremely large N, though unlikely with the given constraints.
An alternative optimal approach using Breadth-First Search (BFS). Instead of recursion, this iterative approach explores the employee hierarchy level by level, starting from the head. It keeps track of the cumulative time taken for the news to reach each employee.
Algorithm
- Build an adjacency list
adjfrom themanagerarray. - Initialize a queue and add a pair
(headID, 0), representing(employeeID, timeToReach). - Initialize
maxTime = 0. - While the queue is not empty:
- Dequeue the current employee
uand their arrival timetimeU. - Update the overall maximum time:
maxTime = Math.max(maxTime, timeU). - Calculate the arrival time for direct subordinates:
timeForSubordinates = timeU + informTime[u]. - For each subordinate
vofu:- Enqueue the pair
(v, timeForSubordinates).
- Enqueue the pair
- Dequeue the current employee
- After the loop finishes, return
maxTime.
Walkthrough
Similar to the DFS approach, we first build an adjacency list to represent the tree. We use a queue to perform the BFS, which will store pairs of (employeeID, timeToReach). We initialize the queue by adding the head of the company: queue.add(new int[]{headID, 0}). The time to reach the head is 0. We also maintain a variable maxTime to keep track of the maximum time encountered so far. The BFS proceeds by dequeuing an employee u and their timeToReach, updating maxTime, and then enqueuing all of u's subordinates with their calculated arrival time (timeToReach + informTime[u]). After the BFS completes, maxTime will hold the time the last employee gets the news, which is the answer.
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue; class Solution { public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { List<List<Integer>> adj = new ArrayList<>(n); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { if (manager[i] != -1) { adj.get(manager[i]).add(i); } } Queue<int[]> queue = new LinkedList<>(); // Queue stores {employeeID, timeToReachThisEmployee} queue.offer(new int[]{headID, 0}); int maxTime = 0; while (!queue.isEmpty()) { int[] current = queue.poll(); int u = current[0]; int timeU = current[1]; maxTime = Math.max(maxTime, timeU); int timeForSubordinates = timeU + informTime[u]; for (int v : adj.get(u)) { queue.offer(new int[]{v, timeForSubordinates}); } } return maxTime; }}Complexity
Time
O(N). Building the adjacency list takes O(N). The BFS traversal visits each node and edge once, which is also O(N).
Space
O(N). The adjacency list takes O(N) space. The queue can store up to the maximum number of nodes at any level of the tree (the tree's width), which can be O(N) in the worst case (e.g., a star graph).
Trade-offs
Pros
Optimal O(N) time complexity.
Iterative approach, which avoids potential stack overflow issues from deep recursion.
Processes each employee exactly once.
Cons
Requires O(N) extra space for both the adjacency list and the queue.
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; }}class Solution {private List<Integer>[] g;private int[] informTime;public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); this.informTime = informTime; for (int i = 0; i < n; ++i) { if (manager[i] >= 0) { g[manager[i]].add(i); } } return dfs(headID); }private int dfs(int i) { int ans = 0; for (int j : g[i]) { ans = Math.max(ans, dfs(j) + informTime[i]); } return ans; }}class Solution {public: int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> &informTime) { vector<vector<int>> g(n); for (int i = 0; i < n; ++i) { if (manager[i] >= 0) { g[manager[i]].push_back(i); } } function<int(int)> dfs = [&](int i) -> int { int ans = 0; for (int j : g[i]) { ans = max(ans, dfs(j) + informTime[i]); } return ans; }; return dfs(headID); }};class Solution: def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int: def dfs(i: int) -> int: ans = 0 for j in g[i]: ans = max(ans, dfs(j) + informTime[i]) return ans g = defaultdict(list) for i, x in enumerate(manager): g[x]. append(i) return dfs(headID)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.